For elastic collisions of n particles, we know that momentum in the three orthogonal directions are independently conserved:$$ \frac{d}{dt}\sum\limits_i^n m_iv_{ij} =0,\quad j=1,2,3$$
From this, it follows there's also a corresponding scalar quantity conserved:$$\frac{d}{dt}\sum\limits_i^n m_i(v^2_{i1} + v^2_{i2} + v^2_{i3}) = \frac{d}{dt}\sum\limits_i^n m_iv^2_i =0,\quad j=1,2,3$$
So why is there a need to put 1/2 in front of this conserved scalar quantity, kinetic energy?
The factor of $1/2$ is required from Galilean invariance, so that the energy mixes up with the momentum without a factor. This was understood before relativity, but it is largely conventional before relativity, since you could make the energy mix up with the momentum using some coefficient. Once you have relativity, the $1/2$ is no longer optional.
I'll start with relativity. The kinetic energy formula is the extra energy in a moving particle
$$ {m\over \sqrt{1-v^2}} = m + {mv^2\over 2} + \cdots$$
in units where c=1. The one half comes from the expansion of the geometrical square root, and the square-root form in the denominator is uniquely and naturally fixed by requiring that the energy and momentum fit together into a four vector. This is the only natural definition in relativity, and it is justified by geometry.
In Newtonian mechanics, the energy and momentum transform together after a Galilean boost. If you have a closed system with momenta $p_i$ that add up to zero (center of mass frame), the change in the kinetic energy after a boost, which shifts $p_i\rightarrow p_i - m_i v$ is
$$\sum_i {p_i^2\over 2m_i} \rightarrow \sum_i \frac{m_i}{2}~(v_i - v)^2 = \sum_i {p_i^2\over 2m_i} - \sum_i p_i \cdot v + \sum_i m_i {v^2\over 2} $$
The change has two parts,
$$ \left(\sum_i p_i \right) \cdot v $$
This is the mixing of energy and momentum, and this part is the total momentum dot the velocity, and it is zero when you start in the CM frame. The other part is:
$$ \left(\sum_i m_i \right) {v^2\over 2} $$
This part is the total mass times half the square of the velocity, or the total kinetic energy added to the object by boosting it. You see that you get the right answer, the total mass times the center of mass velocity, now that the center of mass is moving. If the object was already moving, it is nontrivial to ensure that you get the right answer--- the new center of mass velocity squared times the total mass squared--- for the new energy.
This requirement, that the energy is consistent under galilean boosts, is what is meant by the mixing of momentum and energy. It is simplest if you take the coefficient $1/2$, ultimately because this is the natural nonrelativistic limit of relativity. You would have a factor of $2$ in the $p$ mixing term if you didn't take the coefficient $1/2$. It is actually a testiment to the insight of the 19th century physicists that they adopted the most natural convention before relativity was discovered.
The half in the non-relativistic kinetic energy can be traced back to the Work-Energy Theorem$^1$.
Of course, if one is only interested in solving an elastic collision problem for an isolated system of point particles using momentum and kinetic energy conservation, no harm is done by multiplying the energy conservation equation with a factor 2 on both sides of the equation.
--
$^1$ Here we assume that the standard formulas for work $W=\int {\bf F}\cdot d{\bf r}$, Newton's 2nd law ${\bf F}=m{\bf a}$, acceleration ${\bf a}=\dot{\bf v}$, velocity ${\bf v}=\dot{\bf r}$, etc, hold without unconventional normalization factors.
The reason is because of the Work-Energy theorem, which states that if a force is applied on an object over a distance, that the integral of the force along the distance, or the work applied on the object, must equal the change in the kinetic energy, as the energy transferred through work must be conserved. So for an object at rest, if a force $F$ is applied in one dimension over a distance $x$, its change in kinetic energy is given by the work done on the object: $$E_k - 0 = \int_{0}^{x} {F \cdot dx}$$ (We have the change in kinetic energy represented by $E_k$ as the final kinetic energy, and $0$ as the initial kinetic energy.) If we manipulate the integral using $F = ma$, it becomes $$E_k = \int_{0}^{x} {ma \cdot dx}$$ We can multiply by $\frac{dt}{dt}$ in the integral, and it becomes $$E_k = \int_{0}^{x} {ma \hspace{2pt} dt \cdot \frac{dx}{dt}}$$ Since we know that $v = \frac{dx}{dt}$, and that $a = \frac{dv}{dt}$, $a \hspace{2pt} dt$ becomes $dv$, and $\frac{dx}{dt}$ becomes $v$. This turns the integral into: $$E_k = \int_{0}^{v} {mv \cdot dv}$$ We now integrate from $0$ to $v$ because we've turned the integral into an integral over position into an integral over velocity. Since integrating a linear function $kx$ with respect to $x$ gives $\frac{1}{2} kx^2$, the expression becomes: $$E_k = \frac{1}{2} mv^2$$
So basically, the Work-Energy theorem as well as manipulating the integral is the reason for the $\frac{1}{2}$ in $\frac{1}{2} mv^2$.
Kinetic Energy ($\mathrm{KE}$) is equal to work done, $\mathrm{KE} = W$, and work is equal to force ($F$) applied to a body multiplied by the distance ($d$) it travels, or $W = Fd$. Since $F = ma$, the former equation renders $W = mad$.
Providing that acceleration is uniform and the initial velocity is zero, suppose there is a graph with velocity $v$ on the $y$-axis and time ($t$) on the $x$-axis. Furthermore there is a line passing through the origin and has a slope equal to the acceleration of the body. For a given interval of time, the distance traveled by the body is equal to the area under the line and that is $d = vt/2$. If we substitute $d$ into $W = mad$ we get $W = mavt/2$ (notice how the half has appeared). The equation becomes $W = matv/2$ but since $at = v$ we get $$ W = \mathrm{KE} = \frac{1}{2} mv^2. $$
See the below diagram where the equation of the line (i.e. a lineal function) has a slope equal to the acceleration of a body. Recall the y-intercept form of equation for a line or $y = mx + b$, where $m$ represents slope and $b$ represents the y-intercept or initial velocity. Notice also the shape of the area $d$ is that of a right triangle. This means, $$v = at$$
In addition to the other answers, bear in mind that $ E = \frac 1 2 m v^2 $ is a quadratic form.
Quadratic forms arise whenever you integrate an $f(x) = k\cdot x$ function.
Examples:
$$ E_{kin} = \int m v\; \mathrm d v = \tfrac 1 2 m v ^ 2 \\ A_\circ = \int \tau r \; \mathrm d r = \tfrac 1 2 \tau r^2 \quad \tau = 2\pi \\ E_{spring} = \int k x \;\mathrm d x = \tfrac 1 2 k x^2 \\ v = \int a t \;\mathrm d t = \tfrac 1 2 a t^2$$
In Special Relativity velocity's additive group is not the Reals, so you get a different result of that integration.
The same reason why distance is half the acceleration I have my own ways of answering the question since i don't know calculus. Anyway
$w = mda$, assuming you know distance and acceleration(for now)
$d = \frac{1}{2}at^2$
$\frac{2d}{a}= t^2$
$\sqrt{\frac{2d}{a}}= t$
multiplying the time t by acceleration a gives us the velocity
$v = \sqrt{\frac{2d}{a}}a$
$v = \frac{\sqrt{{2d}}}{\sqrt{a}} a$
$v = \sqrt{2d}\sqrt{a}$
$v = \sqrt{2da}$ and da equals work over mass so
$v = \sqrt{\frac{2w}{m}}$
$v^2 =\frac{2w}{m} $
$mv^2 =2w$
$w = \frac{1}{2}mv^2$
Kinetic energy isolates the energy associated directly with the vector motion of a specific object, and excludes the offsetting momentum to other objects which must necessarily exist, in the opposite direction, in order to satisfy Newton's third law.
The sum of all of the kinetic energy created across all objects equals the amount of energy so applied, but since any single object (used very loosely) can only "own" the one-half of the energy associated with its total greater momentum-neutral motion, that is therefore also all that it can transmit by passing on its own momentum in a collision.
Other forms of energy capture the total energy required to create motion in a momentum neutral fashion. Notably, gravitational potential energy includes both the motion associated with an object falling down to earth, and the much smaller, but still momentum-equal, motion of the earth rising up to meet the object. Thus the existence of the one-half convention. Related: Gravity and KE
In classical physics: $$\begin{align*} W&=\int_{\vec s_1}^{\vec s_2}\vec F\cdot d\vec s\\ &=\int_{t_1}^{t_2}m\frac{d\vec v}{dt}\cdot\vec v dt\\ &=m\int_{t_1}^{t_2}\frac12\frac{d}{dt}\left(\vec v\cdot\vec v\right)dt\\ &=\frac12m\int_{t_1}^{t_2}\frac{d}{dt}\left(||\vec v||^2\right)dt\\ &=\frac12m||\vec v(t_2)||^2-\frac12m||\vec v(t_1)||^2\\ \end{align*}$$ $$\frac{d}{dt}\left(\vec v\cdot\vec v\right)=\frac{d\vec v}{dt}\cdot\vec v+\vec v\cdot\frac{d\vec v}{dt}=2\frac{d\vec v}{dt}\cdot\vec v$$
