Sharing my understanding:

If one starts with Newton's 2nd law (F=ma) assumed, then one can derive kinetic energy to be 0.5mv^2, and this is what most of the answers are explicitly or tacitly doing.

One could however start with Lagrangian formulation along with KE = 0.5mv^2 and drive F=ma. This is where one needs an explanation for why KE = 0.5mv^2, and the first answer (@Ron Maimon) is providing an explanation.

Most books I have come across on Lagrangian formulation secretly assume Newton's laws.

In my opinion, Lagrangian formulation can proceed without Newton's and without even defining momentum as mv, however, now needs KE = 0.5mv^2.