The previous answers all restate the problem as "Work is force dot/times distance". But this is not really satisfying, because you could then ask "Why is work force dot distance?" and the mystery is the same.
The only way to answer questions like this is to rely on symmetry principles, since these are more fundamental than the laws of motion. Using Galilean invariance, the symmetry that says that the laws of physics look the same to you on a moving train, you can explain why energy must be proportional to the mass times the velocity squared.
First, you need to define kinetic energy. I will define it as follows: the kinetic energy $E(m,v)$ of a ball of clay of mass $m$ moving with velocity $v$ is the amount of calories of heat that it makes when it smacks into a wall. This definition does not make reference to any mechanical quantity, and it can be determined using thermometers. I will show that, assuming Galilean invariance, $E(m,v)$ must be the square of the velocity.
$E(m,v)$, if it is invariant, must be proportional to the mass, because you can smack two clay balls side by side and get twice the heating, so
$$E(m,v) = m E(v)$$Further, if you smack two identical clay balls of mass $m$ moving with velocity $v$ head-on into each other, both balls stop, by symmetry. The result is that each acts as a wall for the other, and you must get an amount of heating equal to $v$.
But now look at this in a train which is moving along with one of the balls before the collision. In this frame of reference, the first ball starts out stopped, the second ball hits it at $2v$, and the two-ball stuck system ends up moving with velocity $v$.
The kinetic energy of the second ball is $mE(2v)$ at the start, and after the collision, you have $2mE(v)$ kinetic energy stored in the combined ball. But the heating generated by the collision is the same as in the earlier case. So there are now two $2mE(v)$ terms to consider: one representing the heat generated by the collision, which we saw earlier was $2mE(v)$, and the other representing the energy stored in the moving, double-mass ball, which is also $2mE(v)$. Due to conservation of energy, those two terms need to add up to the kinetic energy of the second ball before the collision:
$$mE(2v) = 2mE(v) + 2mE(v)$$ $$E(2v) = 4 E(v)$$which implies that $E$ is quadratic.
Non-circular force-times-distance
Here is the non-circular version of the force-times-distance argument that everyone seems to love so much, but is never done correctly. In order to argue that energy is quadratic in velocity, it is enough to establish two things:
The result then follows.
That the energy in a constant gravitational field is proportional to the height is established by statics. If you believe the law of the lever, an object will be in equilibrium with another object on a lever when the distances are inversely proportional to the masses (there are simple geometric demonstrations of this that require nothing more than the fact that equal mass objects balance at equal center-of-mass distances). Then if you tilt the lever a little bit, the mass-times-height gained by 1 is equal to the mass-times-height gained by the other. This allows you to lift objects and lower them with very little effort, so long as the mass-times-height added over all the objects is constant before and after.This is Archimedes' principle.
Another way of saying the same thing uses an elevator, consisting of two platforms connected by a chain through a pulley, so that when one goes up, the other goes down. You can lift an object up, if you lower an equal amount of mass down the same amount. You can lift two objects a certain distance in two steps, if you drop an object twice as far.
This establishes that for all reversible motions of the elevator, the ones that do not require you to do any work (in both the colloquial sense and the physics sense--- the two notions coincide here), the mass-times-height summed over all the objects is conserved. The "energy" can now be defined as that quantity of motion which is conserved when these objects are allowed to move with a non-infinitesimal velocity. This is Feynman's version of Archimedes.
So the mass-times-height is a measure of the effort required to lift something, and it is a conserved quantity in statics. This quantity should be conserved even if there is dynamics in intermediate stages. By this I mean that if you let two weights drop while suspended on a string, let them do an elastic collision, and catch the two objects when they stop moving again, you did no work. The objects should then go up to the same total mass-times-height.
This is the original demonstration of the laws of elastic collisions by Christian Huygens, who argued that if you drop two masses on pendulums, and let them collide, their center of mass has to go up to the same height, if you catch the balls at their maximum point. From this, Huygens generalized the law of conservation of potential energy implicit in Archimedes to derive the law of conservation of square-velocity in elastic collisions. His principle that the center of mass cannot be raised by dynamic collisions is the first statement of conservation of energy.
For completeness, the fact that an object accelerates in a constant gravitational field with uniform acceleration is a consequence of Galilean invariance, and the assumption that a gravitational field is frame invariant to uniform motions up and down with a steady velocity. Once you know that motion in constant gravity is constant acceleration, you know that
$$\frac{{mv}^{2}}{2} + mgh = C$$so that Huygens dynamical quantity which is additively conserved along with Archimedes mass times height is the velocity squared.