Motivating the non-relativistic momentum $$\mathbf{p} = m\mathbf{v}$$ is quite easy: it is meant to represent the quantity of motion of the particle, and since the mass is one measure of quantity of matter it should be proportional to mass (how much thing is moving) and should be proportional to velocity (how fast and to where it is moving).
Now, in Special Relativity the momentum changes. The new quantity of motion becomes
$$\mathbf{p} = \dfrac{m\mathbf{v}}{\sqrt{1-\dfrac{v^2}{c^2}}}$$
Or, using $\gamma$ the Lorentz factor $$\mathbf{p} = \gamma(v) m\mathbf{v}$$ where I write $\gamma(v)$ to indicate that the velocity is that of the particle relative to the frame in which the movement is being observed.
The need for this new momentum is because the old one fails to be conserved and because using the old one in Newton's second law leads to a law which is not invariant under Lorentz transformations. So the need for a new momentum is perfectly well motivated.
What I would like to know is how can one motivate that the correct choice for $\mathbf{p}$ is the $\gamma(v)m\mathbf{v}$. There are some arguments using the mass: considering a colision, requiring momentum to be conserved, transform the velocity and then find how mass should transform. Although this work, it doesn't seem natural, and it is derived in one particular example.
On my book there's even something that Einstein wote saying that he didn't think it was a good idea to try transforming the mass from $m$ to $M = \gamma(v)m$, that it was better to simply keep $\gamma$ on the new momentum without trying to combine it with the mass.
So I would like to know: without resorting to arguments based on transformation of the mass, how can one motivate the new form of momentum that works for special relativity?