Why is $E=mc^2$ and not $E=m\frac{c^2}{2}$? Kinetic energy for a moving object is the integral of force with respect to distance, often given as:
$$E=m\frac{v^2}{2}.$$
This would imply that for mass moving at the speed of light, the kinetic energy would be:
$$E=m\frac{c^2}{2}.$$
This puts it off from the Einstein result by a factor of two. Why the discrepancy?
 A: As the other answers point out, the full relativistic energy expression is
$$E^2=m^2c^4+p^2c^2$$
where $E$ is the energy, $m$ is the rest mass of the particle, $c$ is the speed of light and $p$ is the momentum of the particle.
If the particle isn't moving (i.e. has $p=0$) then this expression reduces to the famous
$$E=mc^2$$
which describes the rest energy of the particle (note this has nothing to do with the kinetic energy, which is $0$ for a particle at rest).
We can obtain the classical formula $E_\text{kinetic}\approx\frac{1}{2}mv^2$ in the following way...
Write the above general energy expression as
$$E^2=m^2c^4\left(1+\frac{p^2}{m^2c^2}\right)$$
and then take the square root:
$$E=mc^2\left(1+\frac{p^2}{m^2c^2}\right)^{1/2}$$
For a slow moving particle (i.e. one that isn't relativistic, $v\ll c$), one finds that $p$ is quite a lot smaller than the quantity $mc$.  This is because the relativistic momentum is given by $p=\gamma mv\approx mv$, where $\gamma=\left(1-\frac{v^2}{c^2}\right)^{-1/2}\approx1$ for a non-relativistic particle, and so the ratio $\frac{p^2}{m^2c^2}\approx\frac{v^2}{c^2}\ll1$.
This means we can binomially expand the above energy expression (valid if $\frac{p^2}{m^2c^2}\approx\frac{v^2}{c^2}\ll1$), giving
\begin{align}
E&\approx mc^2\left(1+\frac{p^2}{2m^2c^2}+...\right)\\&\approx mc^2\left(1+\frac{m^2v^2}{2m^2c^2}\right)\\&\approx mc^2\left(1+\frac{v^2}{2c^2}\right)\\&\approx mc^2 + \frac{1}{2}mv^2
\end{align}
We see we've obtained the total energy of the particle as the sum of the rest energy (which it always has), and the non-relativistic kinetic energy (valid if $v\ll c$).
A: $E=mc^2$ isn't supposed to be the body's kinetic energy. In that equation, $c$ is the speed of light, but in the formula for kinetic energy, $c$ (or preferably $v$ is the velocity of the body. Furthermore, there's no body which can be accurately described as having kinetic energy $E=\frac{1}{2}mc^2$, because that implies a massive body travelling at the speed of light.
A: You cannot make this 1:1 correspondence between the classic kinetic energy of a particle and the rest energy of a relativistic particle.
$E = mc^2$ does not apply only to objects moving at the speed of light, but instead to all objects, moving or not. As such, it isn't a relativistic correction of the kinetic energy, but describes the rest energy of a particle.
The relativistic energy of a moving particle is given (from special relativity) by $$E^2 = m^2 c^4 + p^2 c^2$$
This can further be simplified to $$E = \gamma m c^2,$$ where $\gamma = \frac{1}{\sqrt{1-\beta^2}}$ (the Lorentz factor) and $\beta = \frac{v}{c}$.
$\gamma$ is $1$ if the object is at rest, which reduces this to the famous $$E = mc^2$$
