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
Newton's second law
As you probably know, Newton thought that energy is linearly proportional to velocity: the Latin terms vis [force] and potentia [potence, power] were used at that time to refer to what today is called energy. The second law's original formulation reads: "Mutationem motus proportionalem esse vi motrici impressae" = "any change of motion (velocity) is proportional to the motive force impressed".
This law, which nowadays is wrongly interpreted as: $F = ma$ (there is no reference to mass here) simply states states: $$[\Delta/\delta v]( v_1-v_0) \propto Vis_m$$ and in modern terms is sometimes (illegitimately) also interpreted as impulse, sort of : $$\Delta v \propto J [/m] \rightarrow \Delta p = J$$. But mass is not at all mentioned in the second law (as the original text shows) but only in the second definition, where we can see a definition of momentum as 'the measure of [quantity of] motion'
and, moreover 'motive force' (vis motrix) is used, like all other scholars of the time, referring to the yet unknown kinetic 'force' that made bodies move, which Galileo had called 'impeto' and Leibniz 'motive power'. The interpretation of this formula as the definition of force in modern usage is an ex post facto historical manipulation, done against the author's own will: he knew about this interpretation proposed by Hermann and refused to adopt it in the final edition
The historical facts
It was Gottfried Leibniz, as early as 1686 (one year before the publication of the Principia) who first affirmed that kinetic energy is proportional to squared velocity or that velocity is proportional to the square root of energy: $$ v \propto \sqrt{V_{viva}}$$. He called it, a few years later, vis viva = 'a-live/living' force in contrast with vis mortua = 'dead' force: Cartesian momentum ([mass/weight =] size * speed: $m *|v|$). This was accompanied by a first formulation of the principle of conservation of kinetic energy, as he noticed that in many mechanical systems of several masses $m_i$ each with velocity $v_i$,
$\sum_{i} m_i v_i^2$
was conserved so long as the masses did not interact. The principle represents an accurate statement of the approximate conservation of kinetic energy in situations where there is no friction or in elastic collisions. Many physicists at that time held that the conservation of momentum, which holds even in systems with friction, as defined by the momentum: $\,\!\sum_{i} m_i v_i$ was the conserved kinetic energy.
The concept of PE played no role, it did not exist yet, nor did the concept of mechanical energy to which you refer (E = U + V), but Leibniz, in this first paper, uses the term potentia motrix/ viva [motive power] to refer both to the energy a body acquires falling from an altitude and to the force necessary to lift it to the same altitude (mass/weight * space: $F*s$) which are considered equal. Some scholars see, wrongly, here a first definition of PE, but that is simply one of the axioms of Galileo.
The principle to which you refer: $E_{mech} [KE + PE] = k$ in astrodynamics is called vis viva equation in his honour. Leibniz stated the conservation of KE per se besides the conservation of all (kinds of) energy in the whole universe. We need to underline this amazing stroke of genius.
His theory was strongly adversed by Newton[ians] and DesCartes-ians because it seemed to contrast, to be incompatible with the conservation of momentum. In Newton there was no distinction (as shown above) between speed, motion, momentum and energy but quantitas motus (momentum) was the prevailing concept and it was proven to be conserved in all situations, therefore Leibniz' vis viva was considered a threat to the whole system. Only later it was acknowledged that both energy and momentum, being different entities, could be conserved (by Bošković and later (1748) by d'Alembert).
That's overlooking historical facts (Joule was not concerned with KE): soon after Leibniz' death, the quadratic relation was confirmed by experiments independently by the Italian Poleni in 1719 and the Dutch Gravesande in 1722, who dropped balls from varying heights onto soft clay and found that balls with twice speed produced and indentation four times deeper. The latter informed M.me du Châtelet of his results and she publicized them. Two centuries later, after Joule had shown that mechanical work can be transformed in heat, Helmholz suggested that the lost energy, in inelastic collisions, might have been transformed in heat.
Thomas Young is thought to have been the first to substitute the terms 'vis viva/ potentia motrix' with 'energy' in 1807 (from the Greek word: ἐνέργεια energeia, which had been coined by Aristotle on the stem of ergon = work, therefore: energeia [= the-state-of-being-at-work]). Later (1824-1829) Coriolis introduced the current formula and the terms 'work' and 'semi-vis viva'; this concept and the consequent theory of conservation of energy was eventually formalized by Lord Kelvin, Rankine et al. in the field of thermodynamics.
The formula of kinetic energy
The question is much more complex than it appears, as there are at least four formulas involved here, and each issue is complex in its turn:
I did not want to make this post too long, but I'll take the suggestion from the bounty and address the issues in separate answers. Just a brief note here to make this post self-contained: the formula of KE was not derived from work, as it may seem: it's the other way round. $W = F * d$ and $F = m * a$ were by-products of the KE formula. Once the quadratic relation had been verified and universally accepted: $E \propto v^2$, any coefficient (0.2, 0.5, 2..) could be added as an irrelevant and arbitrary choice that depended only on the choice of units.
The only avalaible (and precisably measurable) source of KE at the time was gravity and the Galilean equations were too strong a temptation, as they included, too, a [0.5] quadratic relation: it seemed a stroke of genius to make the energy of the unitary mass at unitary (uniform) acceleration coincide with space. In this way energy was simply the integration of [m] $g$ on space.
Conclusions
Tying energy to gravity, that is, to acceleration and in particular to constant acceleration was not a wise idea, it was a gross mistake that tied, confined newtonian mechanics in a strait-jacket because it was in this way unable to deal with the more natural situations when KE is related to velocity and when there is just a transfer of energy: the concept of impulse was just an ad hoc awkward attempt to deal with that.
Tying work-energy to space and not to the mere transfer of energy was an insane decision that had irrational, catastrophic practical consequences. But consequences were even more devastating on the conceptual, theoretical level because explaining and identifying KE with the acceleration gave the illusion that the issue of motion-KE had been understood, and prevented further speculation.
Leibniz invented the concept of (kinetic) energy, prefigured and discovered its real formula $E = v^2$ resisting the Siren of gravity, suggested the right way of integration and established the universal principle of 'conservation of energy' as prevailing on/independent from 'conservation of momentum' (transcending Huygens' principle of 'conservation of KE').
He engaged in passionate controversies until his death but was opposed and overwhelmed by obtuse/ignorant Newtonian contemporaries. He was vulnerable as he could not account for the loss of energy in inelastic collisions. He lost, and newtonian integration on space produced: $\frac{1}{2}$ mv2 which is not the formula, but just one of the possible formulas of KE: the newtonian formula. Had he won, instead of the joule, now we would use the 'leibniz' (= 1/2 J) and we would have a different, probably deeper, insight into the laws of motion and of the world.
You can find additional information on work here