Relativistic momentum I have been trying to derive why relativistic momentum is defined as $p=\gamma mv$. 
I set up a collision between 2 same balls ($m_1 = m_2 = m$). Before the collision these two balls travel one towards another in $x$ direction with velocities ${v_1}_x = (-{v_2}_x) = v$. After the collision these two balls travel away from each other with velocity ${v_1}_y = (-{v_2}_y) = v$. Coordinate system travells from left to right with velocity $u=v$ at all times (after and before collision). 
Please see the pictures below where picture (a) shows situation before collision and picture (b) after collision.

Below is a proof that Newtonian momentum $mv$ is not preserved in coordinate system $x'y'$. I used $[\, | \,]$ to split $x$ and $y$ components. $p_z'$ is momentum before collision where $p_k'$ is momentum after collision.
$$
\scriptsize
\begin{split}
p_z' &= \left[ m_1 {v_1}_x' +  m_2 {v_2}_x'\, \biggl| \, 0 \right] = \left[ m_1 0 +  m_2 \left( \frac{{v_2}_x - u}{1-{v_2}_x\frac{u}{c^2}}  \right)\, \biggl| \, 0 \right]= \left[ m \left( \frac{-v - v}{1+ v \frac{v}{c^2}}  \right) \, \biggl| \, 0 \right] \\
p_z' &= \left[ - 2mv \left( \frac{1}{1+ \frac{v^2}{c^2}}\right) \, \biggl| \, 0 \right]
\end{split}
$$
$$
\scriptsize
\begin{split}
p_k' &= \left[-2mv  \, \biggl| \,m_1 {v_1}_y' + m_2 {v_2}_y'\right]=\left[ -2mv \, \biggl| \, m_1 \left( \frac{{v_1}_y}{\gamma \left(1 - {v_1}_y \frac{u}{c^2}\right)}  \right) + m_2  \left( \frac{{v_2}_y}{\gamma \left(1 - {v_2}_y \frac{u}{c^2}\right)}  \right) \right]\\
p_k' &= \left[ -2mv \, \biggl| \, m \left( \frac{v}{\gamma \left(1 - v \frac{v}{c^2}\right)}  \right) - m  \left( \frac{v}{\gamma \left(1 - v \frac{v}{c^2}\right)}  \right)\right]\\
p_k' &= \left[ -2mv \, \biggl| \, 0 \right]
\end{split}
$$
It is clear that $x$ components differ by factor $1/\left(1+\frac{v^2}{c^2}\right)$.
QUESTION: I want to know why do we multiply Newtonian momentum $p=mv$ by factor $\gamma = 1/ \sqrt{1 - \frac{v^2}{c^2}}$ and where is the connection between $\gamma$ and factor $1/\left(1+\frac{v^2}{c^2}\right)$ which i got?
 A: 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.
A: Relativistic momentum is not defined as $p= \gamma m v$. For instance, this expression does not apply to photons, which are massless particles [*].
In the Lagrangian formalism of mechanics the momentum is defined as
$$p\equiv \frac{\partial L}{\partial v}$$
Using the relativistic Lagrangian for a free massive particle
$$L = - m c^2 \sqrt {1 - \frac{v^2}{c^2}} $$
we obtain $p= \gamma m v$ from the definition.
The conservation laws can be obtained by using the ordinary Lagrangian formalism. For Lagrangians invariant to coordinate transformations, the momentum (as defined above) is automatically conserved. The above Lagrangian for one particle does not depend on coordinates (only on velocity) and, thus, the particle momentum $p$ is conserved. The Lagrangian for two particles does not depend on coordinates (only on velocities) and, thus, the total momentum $p_1 + p_2$ is conserved. If you use non-relativistic Lagrangians you obtain that it is the total non-relativistic momentum which is conserved.
[*] For a photon the relativistic momentum is given by $|p|= E/c^2$.
A: I find it easier to start with notions of four-vectors (momentum and velocity).  Then you can massage these quantities into the usual Newtonian momentum and velocity.  Building up four-momentum the other way around (from $p=mv$) is not obvious at all.
The four-velocity $u = ds/d\tau$ is constrained to have magnitude $c$ under the Minkowski metric.  Take the metric to be $(-,+)$ for $(e_t, e_x)$, basis vectors for a 1+1 space.  Full 3+1 isn't necessary to illustrate what's going on.
We can imagine that a valid four-velocity will have the form $u = ae_t + b e_x$. Forcing that $u \cdot u = -c^2$ implies that $-a^2 + b^2 = -c^2$.  This is satisfied, without any loss of generality, by $a = c \cosh \phi$ and $b = c \sinh \phi$.  That means we have
$$u = \frac{ds}{d\tau} = e_t \frac{d(ct)}{d\tau} + e_x \frac{dx}{d\tau} = c \left( e_t \cosh \phi + e_x \sinh \phi \right)$$
From this we conclude that $dx/d\tau = c \sinh \phi$ and $dt/d\tau = \cosh \phi$.  By the chain rule, it follows that
$$\frac{dx}{dt} = \frac{dx}{d\tau} \frac{d\tau}{dt}$$
By the inverse function theorem, it follows that $d\tau/dt = (dt/d\tau)^{-1}$, so that we have
$$\frac{dx}{dt} = c \frac{\sinh \phi}{\cosh \phi} = c \tanh \phi$$
We then identify that $c \tanh \phi = v$, or $\tanh \phi = \beta$, per the standard terminology in special relativity, for we have found an expression for the conventional three-velocity in terms of $\phi$.  From here, all that remains is to do algebra and use hyperbolic trig identities.  See that
$$\cosh^2 \phi - \sinh^2 \phi = 1 \implies 1 - \tanh^2 \phi = 1/\cosh^2 \phi$$
Put in $\beta = \tanh \phi$ to get
$$\cosh^2 \phi = \frac{1}{1-\beta^2}$$
We choose to define $\gamma = \cosh \phi$, which results in $\sinh \phi = \gamma \beta$.  This makes the four-velocity read
$$u = c (\gamma e_t + \gamma \beta e_x)$$
It's not hard to get to four-momentum from here.  All of this follows naturally from the hyperbolic geometry of spacetime and the requirement that four-velocity have magnitude $c$ for massive objects.
A: In relativistic mechanics, it isn't the 3 dimensional $\vec p$ that is invariant, but the four vector $\bf p$. Therefore, the four momentum $${\bf p} = m {\bf v}$$ where $\bf v$ is the four velocity, and $m$ is the rest mass of the object.
Here, the four velocity is defined as $${\bf v} = \frac {d\vec x}{d\tau}$$ where $\vec x$ is a four vector and $$\tau = \gamma t$$ where $\tau$ is the proper time, which is a Lorentz invariant (the frame-dependent time $t$ and it's time intervals $dt$ are not invariant). 
Now, the four momentum $\bf p$ has components $$(E/c, p_{x}, p_{y}, p_{z}) =  (\gamma mc, \gamma mv_{x}, \gamma mv_{y}, \gamma mv_{z})$$ so we can get back new (relativistically correct) expressions for three momentum and the energy : $$E = \gamma mc^{2}$$
$$\vec p = \gamma m \vec v$$ where $\vec v$ is the three velocity.
I think the error in your calculations arises from the fact that you have to consider the four momentum as invariant, since the three momentum is not invariant under Lorentz transformations.
A: This question goes back to the question that Feynman asked his father about why a ball in a wagon rolled to the back, when he pulled on the wagon. His father replied, "That, nobody knows."
     In other words, you're asking what relativistic momentum is. We don't even know what non-relativistic momentum is. Sure, we know the effects, we measure them, I've measured them in a lab to a ridiculous precision, everybody on this website is giving you equations on the measurable effect of mass increase when you start getting up to a good percentage of the speed of light but, now, eighty-five years or so after Feynman asked his dad the original question, let me repeat his answer:
           That, nobody knows.

What I mean here, is that there is a property of spacetime, called momentum, and not one scientist or layman in the world, knows why, when you start accelerating an object up close to the speed of light, you need to pile on a huge amount of energy, to get it even closer. No one knows why spacetime requires this. And ever since Michelson-Morely, we know that there's no spacetime "drag" or ether that we can measure, that causes this. Obviously, our knowledge of what spacetime "is" has a long way to go, before we can answer the question of what causes momentum, what causes relativistic mass increase. 
