There is no fallacy, you're just not being particularly careful. You need to include both the electric and magnetic forces of the right magnitude and a covariant result drops out.
(Of course historically it went the other way around: people noticed that frame changes were messed up unless the transformation laws were different and this led to the development of special relativity.)
For simplicity let both beams be very thin and have equal uniform charge density $\rho$ in the rest frame and suppose they run exactly parallel separated by a distance $l$. Let the velocity of the beams be $v$ in the lab frame.
Rest frame:
Taking the usual gaussian pillbox gives the electric field of one beam at the location of the other as
$$ \vec{E}_\text{rest} = \frac{\rho}{2\pi\epsilon_0 l} \hat{r}, $$
where $\hat{r}$ is the unit vector directed away from the source beam. Thus the force on a single particle in the second beam (charge $q$) is:
$$ \vec{F}_\text{rest} = \frac{\mathrm{d}p}{\mathrm{d}t_\text{rest}} = \frac{\rho q}{2\pi\epsilon_0 l} \hat{r}. $$
Lab frame:
The charge density of the beam is enhanced by the relativistic $\gamma=1/\sqrt{1-v^2/c^2}$ factor. Thus the electric field is:
$$ \vec{E}_\text{lab} = \frac{\gamma \rho}{2\pi\epsilon_0 l} \hat{r}. $$
There is also a magnetic field of magnitude
$$ B = \frac{\mu_0 \gamma\rho v}{2\pi l} $$
and directed so as to produce an attractive force. Plugging these in the Lorentz force formula
$$ \vec{F}_\text{lab} = q (\vec{E}_\text{lab} + \vec{v}\times\vec{B}) = q\left( \frac{\gamma \rho}{2\pi\epsilon_0 l} - \frac{\mu_0 \gamma\rho v^2}{2\pi l}\right) \hat{r} = \frac{\rho q}{2\pi\epsilon_0 l}\gamma\left(1 - \epsilon_0\mu_0 v^2\right) \hat{r}. $$
Using $\epsilon_0 \mu_0 = c^{-2}$ this reduces to $\vec{F}_\text{lab} = \gamma^{-1} \vec{F}_\text{rest}$ which, on noting the relativistic time dilation $\mathrm{d}t_\text{lab} = \gamma \mathrm{d}t_\text{rest}$, is exactly right! Note that I've used the fact that the force is orthogonal to the velocity implicity when writing the Lorentz transformation law for the force. You can prove the covariance for general motions using the covariant formulation of EM.
Lesson:
Relativity and electromagnetism go together like hand and glove!
