How was the formula for kinetic energy found, and who found it? My questions mostly concern the history of physics. Who found the formula for kinetic energy
$E_k =\frac{1}{2}mv^{2}$
and how was this formula actually discovered?  I've recently watched Leonard Susskind's lecture where he proves that if you define kinetic and potential energy in this way, then you can show that the total energy is conserved. But that makes me wonder how anyone came to define kinetic energy in that way.
My guess is that someone thought along the following lines:

Energy is conserved, in the sense that when you lift something up
  you've done work, but when you let it go back down you're basically
  back where you started. So it seems that my work and the work of
  gravity just traded off.
  But how do I make the concept mathematically rigorous?  I suppose I need functions $U$ and $V$, so that the total energy is their sum $E=U+V$, and the time derivative is always zero, $\frac{dE}{dt}=0$.

But where do I go from here? How do I leap to either


*

*a) $U=\frac{1}{2}mv^{2}$

*b) $F=-\frac{dV}{dt}$? 


It seems to me that if you could get to either (a) or (b), then the rest is just algebra, but I do not see how to get to either of these without being told by a physics professor.
 A: I suspect, though I'm not sure, that a nineteenth century French mathematician and scientist, Gaspard-Gustave Coriolis, is your man. He was the first to define the notion of "work done" and even kinetic energy. His wiki reads:

In 1829 Coriolis published a textbook: Calcul de l'Effet des Machines ("Calculation of the Effect of Machines"), which presented mechanics in a way that could readily be applied by industry. In this period, the correct expression for kinetic energy, ½mv2, and its relation to mechanical work, became established.

I guess that many mathematicians in that era independently found a ½mv2 formula based on Coriolis's work, though it seems likely that Coriolis was the first.
I would guess that the derivations used Coriolis's work-energy theorem:
$$
\textrm{d}W = F \textrm{d}x
$$
Subsituting $F=ma$, one quickly finds that $W=\frac{1}{2} mv^2$:
$$
W = \int ma\,\textrm{d}x = \int m \frac{dv}{dt}\,\textrm{d}x = m\int v \,\textrm{d}v = \frac{1}{2} mv^2.
$$
A: 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'

Quantitas motus est mensura ejusdem (motus) orta ex velocitate et quantite
materiæ conjunctim = 'quantity of motion' (modern 'momentum') is the measure of the same (motion), originated conjunctly by velocity and 'quantity of matter' (total mass)

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).

We can thank Émilie du Châtelet for the modern..understanding of kinetic energy – user121330
There is no energy formula ..in the discovery of
conservation of energy are Joule and... –  Ben Crowell

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:

*

*how, when and by whom was the formula for the second law of motion $F=m*a$ introduced

*how was the formula of kinetic energy $V_{viva} = [m]* v^2$ found by Leibniz

*how, when and by whom was the current newtonian formula of kinetic energy $E_k = [m]*\frac{v^2}{2} $ introduced

*how, when and by whom was the formula for work $W = F*d$ introduced

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.

*

*History, as we know, is written by the victors.
You can find additional information on work here
A: The author of the law of energy conservation was Hermann von Helmholtz (1821-94). See his classic 1847 paper "Über die Erhaltung der Kraft," translated into English as "On the Conservation of Force." (He called energy force.)
A: You've already got some answers, but nobody mentioned Noether's Theorem yet. Noether's theorem maps a conserved quantity to each continuous symmetry. The relevant continuous symmetry needed to prove the conservation of energy is the one that leaves the laws of nature invariant, meaning the laws of physics don't change with time. Each continuous symmetry implies a certain function and the time derivative of that function must be zero. If you wanna read more about it, check out the wikipedia entry or any book about classical mechanics! 
Noether's Theorem on wikipedia.
Note: from the invariance of space (the laws of physics are the same everywhere in space) momentum conservation follows! 
A: The responses given so far are fairly accurate however, the question you should be asking goes to the experimental proof for the kinetic energy formula.  Mathematically, the formulas for work and kinetic energy seem to function perfectly as taught.  Unfortunately, there are at least 2 or 3 situations where it does not.  No physics teacher ever looks at these and so, physics students never get the full story.
I'll give you one scenario that no one will argue against.  Imagine you are performing a space walk and you throw a wrench.  Because the wrench is far less massive than you, it has far more work done to it than you.  If instead of a wrench you threw a small satellite that had the same amount of mass as you did and threw it with the same effort as the wrench, the tossed item would have the same amount of work done to it as was done to you.   The change in kinetic energy for both you and the thrown items would be different; the total ke for you and the wrench would be far more than the ke for you and the satellite even though you used the same amount of biological energy in both cases.
