This answer to a question about why Newtonian kinetic energy is quadratic in velocity shows that if an inelastic collision's KE loss is invariant under Newtonian boosts it has to quadruple when velocity doubles. A simple calculation shows that the famous $\tfrac12mv^2$ formula implies invariance of this loss. If a mass $m_1$'s velocity changes from $v_1$ to $v_1-\frac{m_2}{m_1+m_2}u$ while a mass $m_2$'s velocity changes from $v_2$ to $v_2+\frac{m_1}{m_1+m_2}u$, the total KE reduction is $\frac{m_1m_2}{m_1+m_2}u\cdot(v_1-v_2-\tfrac12u)$, which is invariant under $v_i\mapsto v_i+w$. However, I know of no other reason to expect such invariance. I'm wondering if we can motivate this without the formula, so we can use the above link's reasoning to then derive the quadratic KE-speed relation.
To be fair, the linked answer also argues that energy conservation in a SUVAT approximation of free fall motivates such a quadratic relation. In fact, it can derive not only proportionality to $mv^2$, but the exact expression including the $\tfrac12$ factor. In theory, we can derive the formula that way, then verify invariance, then point out invariance has the implications the answer mentioned earlier. But those are implications we'd already know at that point. To genuinely start from invariance, we need to know why to expect it. (In particular, an individual body's KE change isn't invariant; even the sign of the change isn't.)