Assume that the relativistic momentum is the same as the nonrelativistic momentum you used, but multiplied by some unknown function of velocity $\alpha(v)$.
$$\mathbf{p} = \alpha(v)\,\, m \mathbf{v}$$
Then in the primed frame, the total momentum before the collision is just what you had, but multiplied by $\alpha(v_i)$, with $v_i$ the speed before collision. The momentum after the collision is again what you had, but multiplied by $\alpha(v_f)$, with $v_f$ the speed after the collision.
In order to conserve momentum we must have
$$ \alpha(v_i) \frac{-2mv}{1+v^2} = -2mv \,\alpha(v_f)$$
For simplicity, I'm suppressing factors of $c$.
After the collision, you have a mistake in your velocity transformations. The vertical speed is just $v/\gamma$. That makes the speed of each ball $v_f = (v^2 + (v/\gamma)^2)^{1/2} = v \left(2-v^2\right)^{1/2}$
Plugging in $v_i$ and $v_f$ into the previous equation and canceling some like terms we have
$$ \alpha\left(\frac{2v}{1+v^2}\right) \frac{1}{1 + v^2} = \alpha\left(v[2-v^2]^{1/2}\right)$$
If you let $\alpha(v) = \gamma(v)$ and crunch some algebra you'll see that the identity above is satisfied.
As for your original point, a desire to understand why momentum has a factor $\gamma$ in it, analyzing situations like this one is helpful, but ultimately it is probably best to understand momentum as the spatial component of the energy-momentum four-vector. Since it is a four-vector, it must transform like any other four-vector, $\gamma$'s and all.
There is no contradiction between conservation of momentum and energy and Newton’s 2nd law. Your analysis has one small mistake that makes the conclusion wrong.
Specifically, the conservation of energy does not imply the conservation of kinetic energy. Kinetic energy is not conserved in general. So finding a change in kinetic energy is insufficient to show non-conservation of energy. Instead you would need to show a change in total energy. As others have indicated, in this case the other energy is elastic potential energy. The total energy is conserved.
Now, you might say that kinetic energy is not conserved in general but that kinetic energy is conserved in an elastic collision. So you might say that while the above objection would be correct in general, it doesn’t hold in this specific case.
However, this is a misunderstanding of the meaning of an elastic collision. An elastic collision means that the kinetic energy immediately before the collision is equal to the kinetic energy immediately after the collision. It says nothing about the kinetic energy during the collision. So again, kinetic energy going to elastic potential energy doesn’t contradict the elastic collision constraint either.
Finally, in comments you argued that no elastic potential energy can be stored in an infinitesimal body. This is simply an incorrect claim as a mathematical model. If you write down the actual math you will find that the amount of elastic potential energy stored when $v=0.5 \ \mathrm{m/s}$ is constant and independent of the size of the object, regardless of how small.
Best Answer
You are right, conservation of energy and 1D momentum only give 2 equations, but there are 5 unknowns (the final velocities of all 5 balls), so there are many possible outcomes for a given initial condition. The one with two balls coming out and the two that came in coming to rest seems like it "ought" to be the right one because it's nice and symmetrical, and indeed it's (at least approximately) what we see if we do the experiment, but how does Nature know to pick that one? It turns out, for reasons that are not at all obvious, that you can treat the overall collision as a set of pairwise collisions happening in sequence. It helps to imagine that there's a small gap between the balls, even though in practice they are usually hanging in contact. If we number the balls so that 1 and 2 come in with velocity u and 3, 4, and 5 are initially at rest, first 2 collides with 3, then 3 collides with 4 while 1 collides with 2, then 4 collides with 5 while 2 collides with 3, then 3 collides with 4. The net result is that 1, 2, and 3 are at rest and 4 and 5 exit with velocity u.
Here are the balls' velocities at each step: \begin{eqnarray*} (u, u, 0, 0, 0)\\ (u, 0, u, 0, 0)\\ (0, u, 0, u, 0)\\ (0, 0, u, 0, u)\\ (0, 0, 0, u, u) \end{eqnarray*}
The transmission of the momentum from the left end to the right end happens at the speed of sound in the balls (because it is a compression wave), which for the usual metal balls is so fast as to appear instantaneous (but see this video to see what happens with some other materials).