How can one motivate the relativistic momentum? 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?
 A: Special relativty is about Minkowski spacetime. A line element is given by
$$ ds^2 = c^2dt^2 - dx^2 - dy^2 - dz^2 $$
A free particle will move on a straight line, that is, it will minimize the path length
$$ L = \int ds = \int \sqrt{c^2 \left(\frac{dt}{d\lambda}\right)^2 - \left(\frac{dx}{d\lambda}\right)^2 - \left(\frac{dy}{d\lambda}\right)^2 - \left(\frac{dz}{d\lambda}\right)^2} \ d\lambda$$
where $\lambda$ is an arbitrary parametrisation of the path. We set 
$$ I(\lambda) := \sqrt{c^2 \left(\frac{dt}{d\lambda}\right)^2 - \left(\frac{dx}{d\lambda}\right)^2 - \left(\frac{dy}{d\lambda}\right)^2 - \left(\frac{dz}{d\lambda}\right)^2} $$
The Euler-Lagrange-equations give:
$$ \frac{d}{d\lambda} \left( \frac{\delta I}{\delta \left( \frac{d(ct)}{d\lambda} \right)} \right) - \frac{\delta I}{\delta (ct)} = 0 $$
$$ \frac{d}{d\lambda} \left( \frac{\delta I}{\delta \left( \frac{dx}{d\lambda} \right)} \right) - \frac{\delta I}{\delta x} = 0 $$
etc.
Therefore if we evaluate the differentials and multiply by $I$:
$$ c \frac{d^2t}{d\lambda^2} = 0 $$
$$ - \frac{d^2x}{d\lambda^2} = 0 $$
$$ - \frac{d^2y}{d\lambda^2} = 0 $$
$$ - \frac{d^2z}{d\lambda^2} = 0 $$
Now we parametrisate by proper time $d\lambda = d\tau = \frac{1}{c} ds$, introduce $x_\mu = (ct,-x,-y,-z)^T$ and multiply by $m$. This leaves us
$$ m \frac{d^2x_\mu}{d\tau^2} = 0 $$
the covariant equation of motion of a free particle if we combine all 4 equations.
Using 
$$ d\tau = \frac{1}{c} ds = \frac{1}{c} \sqrt{c^2 dt^2 - dx^2 - dy^2 - dz^2} \\ =  \frac{1}{c} dt \sqrt{c^2 -\left(\frac{dx}{dt}\right)^2 - \left(\frac{dy}{dt}\right)^2 - \left(\frac{dz}{dt}\right)^2} = dt \frac{1}{\gamma(v)} $$
to express by system time $t$, this is equal to:
$$ \frac{d}{dt} \left( m \cdot \gamma(v) \cdot \frac{dx_\mu}{dt} \right) \hat{=} \frac{d}{dt} \left( \matrix{\gamma(v) \cdot m c \\ - m \cdot \gamma(v) \cdot \frac{dx}{dt} \\ - m \cdot \gamma(v) \cdot \frac{dy}{dt} \\ - m \cdot \gamma(v) \cdot \frac{dz}{dt}} \right) \hat{=}  \frac{d}{dt} \left( \matrix{ \gamma(v) \cdot m c \\ - m \cdot \gamma(v) \cdot \vec{v} } \right) = \left( \matrix{0 \\ \vec{0}} \right) $$
The new dynamical quantities are $ \vec{p} = m \cdot \gamma(v) \cdot \vec{v}$, which we may call momentum, and $\frac{E}{c} = \gamma(v) \cdot m c $ where $E$ is energy.
One can now try to add forces on the right side of the equation of motion.
In short: If we start by the assumption that a free particle moves on a straight line in Minkowski space, we are led to new dynamical quantities $\vec{p}$ and $E$ that can be used to describe properties of motion in a similar way as they did in newtonian mechanics.
If one tries to describe nature on basis of tensors, the quantity $\gamma(v) \cdot m$ is not a "good" quantity, as it does not transform like a tensor (e.g scalar). However the quantities $m$ and $(\frac{E}{c}, \vec{p})^T$ are tensors (scalar and contravariant tensor of first rank). So these are the "better" quantities according to the criterion.
A: The Hamiltonian $H$ generates time translations and the momentum $\mathbf p$ generates space translations. In a relativistic theory time and space can mix, so we should consider the 4-vector $$p^\mu = (H, \mathbf p).$$
Now whatever the $\mathbf p$ is in terms of mass, velocity and so on, certainly it is $\mathbf 0$ in a rest frame. Then so that there can be momentum in any frame at all, the time component can't vanish. Thus in a rest frame $$p^\mu = (m, \mathbf 0)$$
for some quantity $m$. Boost to a general frame to conclude that $$p^\mu = (\gamma m, \gamma m \mathbf v).$$
Comparison with the non-relativistic limit shows that $m$ is the mass.
A: This answer is essentially user image's answer using slightly different words:

*

*Argue that a Lorentz-invariant action principle for a massive point particle should be based on proper time,
$$\begin{align} S[x] ~=~&\int\! d\lambda~L, \cr L~=~&\alpha \sqrt{-g_{\mu\nu}\dot{x}^{\mu}\dot{x}^{\nu}}, \cr \dot{x}^{\mu}~:=~&\frac{dx^{\mu}}{d\lambda}, \cr
g_{\mu\nu}~=~&{\rm diag}(-1,1,1,1)
\end{align}\tag{1}$$
up to a proportionality factor $\alpha$.


*Go to static gauge $$\lambda~=~t~=~\frac{x^0}{c}.\tag{2}$$


*Then the Lagrangian reads
$$\begin{align} L~\stackrel{(1)+(2)}{=}&~\alpha\sqrt{c^2-{\bf v}^2}, 
\cr {\bf v}~:=~&\dot{\bf x}.\end{align}\tag{3}$$


*Argue that because the Lagrangian (3) should have dimension of energy, the constant $\frac{\alpha}{m_0c}$ should be dimensionless.


*Argue that to recover the usual non-relativistic limit $|{\bf v}| \ll c$ for the Lagrangian $L$ [up to an irrelevant constant term that cannot be seen in the Lagrange equation, and which turns out to be the rest energy $E_0=m_0c^2$], the constant $$\frac{\alpha}{m_0c}~=~-1\tag{4}$$ must be minus one.


*So we have derived that the Lagrangian is
$$L~\stackrel{(3)+(4)}{=}~-m_0c^2 \sqrt{1-\frac{{\bf v}^2}{c^2}}.\tag{5}$$


*Therefore the canonical/conjugate momentum is
$$\begin{align}{\bf p}~:=~&\frac{\partial L}{\partial {\bf v}}\cr
~\stackrel{(5)}{=}~&\frac{m_0{\bf v}}{\sqrt{1-\frac{{\bf v}^2}{c^2}}},\end{align}\tag{6}$$
and the energy is
$$\begin{align} E~:=~&{\bf p}\cdot {\bf v}-L\cr ~\stackrel{(5)+(6)}{=}&~\frac{m_0c^2}{\sqrt{1-\frac{{\bf v}^2}{c^2}}}, \end{align}\tag{7}$$
which answer OP's question.


*Furthermore, instead of just 1 point particle, we can generalize to a Lagrangian $L=\sum_{i=1}^N L_i$ for $N$ point particles, and we can even introduce interaction and potential terms. If the Lagrangian is invariant under space (explicit time) translations, then according to Noether's theorem, the total momentum (energy) is conserved, respectively.
A: 
What I would like to know is how can one motivate that the correct
  choice for p is the γ(v)mv

In Newtonian mechanics, the momentum of a particle of mass $m$ is given by
$$\mathbf p = m\frac{d {\mathbf r}}{dt} = m \mathbf v$$
where $\mathbf r$ is the position vector and $t$ is a universal parameter.  However, in relativistic mechanics, $t$ is a coordinate, not a parameter, and is thus a component of a four-vector, the four-position $\mathbf R = (ct, \mathbf r)$.
The four-velocity is then defined as
$$\mathbf U = \frac{d \mathbf R}{d \tau} = \frac{d \mathbf R}{d t}\frac{dt}{d\tau} = \frac{d \mathbf R}{d t}\gamma = \gamma (c, \mathbf v) $$
where $\tau$ is the proper time parameter.  In analogy with Newtonian mechanics, the four-momentum is then
$$\mathbf P = m \mathbf U = \gamma m(c, \mathbf v)$$
and then we see that the relativistic momentum is simply the spatial part of the four-momentum.
A: We can deduce the momentum for a 1D world or for a straight path from special relativity and little extra postulate through the following argument.
From Einsteins two postulates we get time and space dilation. Further more energy is force times a movement e.g. assume underneath that we have something like the following,
$$
  E = F \Delta x.
$$
If we postulate that the implicit force is invariant of a change of reference system we conclude that
$$
E = \gamma E_0.
$$
To motivate this an example of such a force assume that we consider a charge moving in a reference frame then the force in the direction of movement is independent of the magnetic field ($F_{mag} = q v\times B$, which is directed orthogonal to the movement) and the electric filed in the direction of the movement is independent for any boost in the direction of the movement which means that the force component in the direction of moment is invariant.
Postulating finally that $E_0 = m c^2$ gives the famous formula for the energy
$$
E = \gamma m c^2
$$
Let's parameterize $\gamma$ differently as
$$
\gamma(-v^2/c^2) = \frac{1}{\sqrt{1-v^2/c^2}}
$$
First of all let's calculate the derivative of the momentum of a particle which are accelerating in a straight path,
$$
\frac{dp}{dt} = \frac{d}{dt}(\gamma(-v^2/c^2) m v) = \gamma^3\frac{m v^2}{c^2} a + \gamma m a = m a \gamma^3\Big (\frac{c^2}{c^2} + (1 - \frac{v^2}{c^2}) \Big ) = m a \gamma^3
$$
The Impulse during this time is
$$
I = F ds = F v \, dt
$$ 
The energy impulse can also be derived by taking the deriviatve of the energy of a moving particle, e.g.
$$
I = \frac{d(\gamma m c^2)}{dt} = \gamma^3\frac{v}{c^2}c^2 m a dt = f^3 v m a \, dt
$$
Comparing now shows that for an acceleration in a straight line we have
$$
F = \frac{d p}{dt},
$$ with
$$
p = \gamma m v
$$
So we derived Newtons second law using
$$
F = \frac{d p}{ dt}
$$
Which implies that the Lagrangian toolbox (which assumes this law) and the associate toolbox can be used.
It feels more natural and basic to postulate that Newton's second law though and use the Lagrangian machinery in other answers this imply that the underlying force hinted at should be Lorenz invariant.
A: All of the prior answers are correct, however they are not Einstein's way of motivating relativistic mechanics.  Whenever I don't find a sufficient answer for the motivation of a physical theory, I find it best to find the pioneer's original publishing of the theory; it provides extremely useful insight into their motivations. Often in modern teachings, material is presented in a diluted, hind-sight biased formulation that, while efficient and well-motivated from a modern perspective, often lacks the original insights to the theory.
Here are three papers. The first is Einstein's original derivation of the mass-energy equivalence from 1905 (just click the image of the paper).
Einstein's Original 1905 $E=mc^2$ Paper
This doesn't contain anything of relativistic mechanics, however, it is only 3 pages, and it sets up his 1935 updated derivation of this principle, in which he intrinsically derives a justification for relativistic momentum from physical and mathematical plausibility arguments.
The third paper is a review paper that discuss the latter paper. I provided it because it gives a guided, condensed version of Einstein's second paper. It's a good reference in case you get stuck within Einstein's original papers.
Einstein 1935, Elementary derivation of the equivalence of mass and energy
Einstein’s 1935 Derivation of $E=mc^2$ - by Francisco Flores
I hope this helped! I would HIGHLY recommend finding original papers if you can when you want the pioneer's original motivations.
