the momentum is the quantity that is conserved as a result of the symmetry with respect to translations. This is the so-called Emmy Noether's theorem.
The only reason why we had $p=mv$ in classical mechanics was that the Lagrangian only depended on $\dot q$ by the kinetic energy $m\dot q^2/2$ term. By the differentiation, you may see that $p=m\dot q$. However, whenever the Lagrangian is different, the relationship between momentum and velocity gets modified.
You quoted one example. Another example is any theory in relativity where
$$ p = \frac{m_0 v}{\sqrt{1-v^2/c^2}} $$
which may also be derived from the Lagrangian. Note that in the relativistic case, the Lagrangian is (minus) the proper time of the world line.
In some cases, the momentum gets modified but people have disagreed what it is. A recently discussed example here was the Abraham-Minkowski controversy about the momentum of a photon in a dielectric material:
Is the Abraham-Minkowski controversy resolved?
For photons, the momentum is $p=E/c$ in the vacuum - this itself is different from massive slow particles - but this relationship can get multiplied or divided by the index of refraction $n$, and arguments arose from this point.
In field theory, one has totally different formulae for the momentum. There are no particles i.e. no velocities of a few objects. Instead, the momentum is distributed in the field - e.g. electromagnetic field - and every region of space carries a momentum density. For example, the momentum density of the electromagnetic field is $\vec E\times \vec H$ or $\vec D\times \vec B$ - which of them is "true" was a famous controversy, equivalent to the controversy about the momentum of a single photon.
Other fields obviously have other formulae for the momentum density.