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
More completely, with $K$ the kinetic energy, $U$ the potential energy and $W$ the work done, then:
$$W=\Delta K+\Delta U$$
If there's no change in $U$ ($\Delta U=0$), then obviously:
$$W=\Delta K$$
Newton's Second Law tells us, with $F$ the force acting on a body of mass $m$, for simplicity's sake we'll consider $F=\text{constant}$:
$$F=ma$$
Let's do this in one dimension, for simplicity's sake, i.e. $x$:
The force causes a displacement $dx$ and performs work $dW$ on the mass $m$:
$$dW=Fdx=madx$$
A little trick:
$$a=\frac{dv}{dt}=\frac{dv}{dx}\frac{dx}{dt}=v\frac{dv}{dx}$$
Insert into $dW$:
$$\implies dW=mvdv$$
So that:
$$\int_0^WdW=\int_{v_1}^{v_2}mvdv$$
$$\boxed{W=\frac12 mv_2^2-\frac12 mv_1^2=\Delta K}$$
As written elsewhere, $W$ can take on any value, positive or negative (or zero). A braking force for instance will act in the opposite sense of the velocity vector and cause deceleration, so that $v_2<v_1$ and $W<0$, $\Delta K<0$. So mind your signs!