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.
Momentum is conserved in magnitude and direction. So in order to analyze any situation of momentum conservation, you should always start with
$$
\sum \mathbf p_{i}=\sum\mathbf p_f
$$
where the subscripts denote the initial and final momenta.
As to the ball & wall, you are correct that momentum is not conserved if you are only looking at the ball. If you consider that the system includes the wall, then the momentum conservation holds. This does mean that the wall contains a momentum of $2mv$ (for mass $m$ and velocity $v$). But note that since the mass of the wall is incredible compared to the ball, the velocity is notably imperceptible!
Best Answer
That's incorrect because you must subtract the quantities in order to obtain the difference between, i.e., by how much it changed.
That becomes clear when considering $\vec{p}=\text{const.}$, say, $\vec{p}=3\hat{\imath}$ in your units; then, according to the quoted text above, the change would be $\Delta \vec{p} = \vec{p}_i +\vec{p}_f = 3\hat{\imath}+3\hat{\imath} = 6\hat{\imath}$, which doesn't make sense, since the change of a constant quantity is zero (since constant means that it doesn't change), which is what you get from your second way of calculating: $$ \Delta \vec{p} = \vec{p}_f -\vec{p}_i.$$
Then, for the constant $\vec{p}$ example, you get $ \Delta \vec{p} = 3\hat{\imath}-3\hat{\imath} = \vec{0}$.