Feynman makes a point of stating explicitly, in vol. 1 of his Lectures on Physics, that $F = \frac{d(mv)}{dt}$ is not the definition of force. In section 12-1 he states
The real content of Newton's laws is this: that the force is supposed
to have some independent properties, in addition to the law $F = ma$;
but the specific independent properties that the force has were
not completely described by Newton or by anybody else, and therefore
the physical law $F = ma$ is an incomplete law. It implies that if we
study the mass times the acceleration and call the product the force,
i.e., if we study the characteristics of force as a program of
interest, then we shall find that forces have some simplicity; the law
is a good program for analyzing nature, it is a suggestion that the
forces will be simple.
I found the following comments from Terence Tao, on the topic of how physics models work, to be enlightening:
Terence Tao - @Pietro: the way mathematical or physical models work,
one assumes the existence of a variety of mathematical quantities
(e.g. forces, masses, and accelerations associated to each physical
object) that obey a number of mathematical equations (such as F=ma),
and one also assumes that the result of various physical measurements
can be computed in terms of these quantities. For instance,
two physical objects A_1, A_2 will be in the same location if and only
if their displacements x_1, x_2 are equal.
Initially, the numerical quantities in these models (such as F, m, a)
are unknown. However, because of their relationships to each other and
tophysical observables, one can in many cases derive their values from
physical measurement, followed by mathematical computation. Using
rulers, one can compute displacements; using clocks, one can compute
times; using displacements and times, one can compute velocities and
accelerations; by measuring the amount of acceleration caused by the
application of a standard amount of force, one can compute masses; and
so forth. Note that in many cases one needs to use the equations of
the model (such as F=ma) to derive these mathematical quantities. (The
use of such equations to compute these quantities however does not
necessarily render such equations tautological. If, for instance, one
defines a Newton to be the amount of force required to accelerate one
kilogram by one meter per second squared, it is a non-tautological
fact that the same Newton of force will also accelerate a two-kilogram
mass by only one half of a meter per second squared.)
If one has found a standard procedure to compute one of these
quantities via a physical measurement, then one can, if one wishes,
take this to be the definition of that quantity, but there are
multiple definitions available for any given quantity, and which one
one chooses is a matter of convention. (For instance, the definition
of a metre has changed over time, to make it less susceptible to
artefacts.)
In some cases, it is not possible to measure a parameter in the model
through physical observation, in which case the parameter is called
"unphysical". For instance, in classical mechanics the potential
energy of a system is only determined up to an unspecified constant,
and is thus unphysical; only the difference in potential energies
between two different states of the system is physical. However,
unphysical quantities are still useful mathematical conveniences to
have in a model, as they can assist in deriving conclusions about
other, more physical, parameters in the model. As such, it is not
necessary that every quantity in a model come with a physical
definition in order for the model to have useful physical predictive
power.
Best Answer
The mechanism is the nature of time and space. Time dilation is certainly an aspect of this.
The usual introductory thought experiment shows that if there is to be a conserved quantity behaving like momentum then its transverse component is invariant between inertial reference frames. But we know that transverse velocity, $u_y=\frac {\Delta y}{\Delta t}$, is not invariant because although $\Delta y$ is invariant, $\Delta t$ is not. But if we replace $\Delta t$ by the invariant interval $\Delta \tau$, then we have an invariant kinematic quantity with the dimensions of velocity. It is easy to show that $$m\frac{\Delta y}{\Delta \tau}=m\gamma(u)\frac{\Delta y}{\Delta t}=m\gamma(u)u_y.$$ Similar expressions must apply for the other momentum components.
The justification of this expression for momentum is not really this thought-experiment, beautiful though it is, but the coherence of the whole fabric of relativistic dynamics. For example, we find that a body's three relativistic momentum components and its energy are the components of a 4-vector with an invariant modulus (mass) exactly analogous to the 4-vector representing the space-time interval between two events.
We also find that, using this definition of momentum, we can express the Lorentz force law in a way that holds in every inertial frame: $$q(\vec E +\vec v \times \vec B)=\frac d{dt}m\gamma(u) \vec u.$$
This is relevant to your statement: "At speed $0.0001c$, force applied is approximately proportional to acceleration. At speed $0.89c$, the same force applied changes the speed of the object very little." I suggest that you look at it a rather different way: it is not the rate of change of $u$ that a force (in the same direction as $\vec u$) is proportional to, but the rate of change of $\gamma(u) u$.