Action is linked to spatial symmetry too, and you can find the square there.

Since space is isotropic, a Lagrangian can only depend on a speed vector through its norm. A Lagrangian must also be decomposable into independent orthogonal components, so you end up with an energy term that is shaped according to:

    f(√(a^2 + b^2)) = f(a) + f(b)

And you end up with f being proportional to v squared.

Note: the components do not need to be independent and orthogonal for this to hold.