What if the kinetic energy of a particle was some other function $f(v)$? This is a "what if this was how the universe worked" kind of question.  I don't know if those belong in Physics StackExchange, and I apologize if they don't.
Suppose we have two reference frames connected by some linear transformation $x'^\mu=\Lambda^\mu_\nu x^\nu$.  In a modern language, we thought the correct $\Lambda^\mu_\nu$ was the Galilean transformation, and we concluded that kinetic energy was $\frac{1}{2} m v^2$.
Later, some smart people (Einstein and others) realized that $\Lambda^\mu_\nu$ should be the Lorentz transformation.  Then, if one assumes momentum conservation and that kinetic energy is a line integral of $\frac{dp}{dt}$, one can reach the conclusion that kinetic energy is $(\gamma -1)mc^2$, which like $\frac{1}{2} m v^2$ is a function of $v^2$.
Now, lets work backwards.  Suppose we lived in an alternate universe, and suppose we knew that the kinetic energy of a particle of mass $m$ is
$$ \text{KE} =  m f(v)$$
where $f(v)$ is a smooth function of $v=|\vec{v}|$.  In the case of non-relativistic classical mechanics, $f(v)=\frac{1}{2}v^2$.
In our alternate universe (with its own symmetries, not necessarily Galilean or Lorentz), with an arbitrary $f(v)$, can we reconstruct the transformation $\Lambda^\mu_\nu$ that connect different frames of reference in our alternate universe?  For every $f(v)$, does an associated $\Lambda^\mu_\nu$ exist?  If so, is it unique?
 A: No, the Lorentz symmetry clearly implies that
$$ E = \frac{mc^2}{\sqrt{1-v^2/c^2}}$$
is the only correct form for energy as a function of the velocity $v$. The only other allowed type of formula is the $c\to\infty$ limit of the abovementioned expression which is
$$ E  = mc^2 + \frac{mv^2}{2}$$
and which contains the latent energy $mc^2$, too. It is the non-relativistic form of the energy. In the non-relativistic limit, the energy is determined up to a shift – only the energy differences are determined – so the velocity-independent term $mc^2$ doesn't spoil anything and may be forgotten in the non-relativistic limit, too. The next term, $mv^2$, is the leading velocity-dependent term in the Taylor expansion.
It's not hard to see that the first formula for energy follows from relativity i.e. that all other formulae are just wrong. The difference
$$ E^2 - p^2 c^2 = m^2 c^4$$
must be an invariant in the same sense in which $(ct)^2-x^2-y^2-z^2$ is an invariant under the Lorentz transformations. Using $pc^2/E=v$ as the expression from the velocity as a ratio of the momentum and the energy, this difference equation is equivalent to the first equation for the energy.
