Must the action be a Lorentz scalar?

First, observe that although the non-relativistic Lagrangian is not invariant. It changes by a total derivative, thus the equations of motions remain invariant. The reason of the difference between the Lorentzian and the Galilean cases is that the group action of the Lorentz group on the classical variables (positions and momenta) is a by means of a true representation, while in the case of the Galilean group the representation is projective. In the Language of geometric quantization, $exp(i \frac{S}{\hbar})$, where $S$ is the action is a section in $L \otimes \bar{L}$, where $L$ is the prequantization line bundle and $\bar{L}$ its dual. In other words, the action needs not be a scalar, only an exprssion of the form: $\bar{\psi}(t_2)exp(i \frac{S(t_1, t_2)}{\hbar})\psi(t_1)$, where $\psi(t)$ is the wavefunction at time $t$ and $S(t_1, t_2)$ is the classical action between $t_1$ and $t_2$. The reason that the representation in the Galilean case is projective is related to the nontriviality of the cohomology group $H^2(G, U(1))$ in the Galilean case in contrast to the Lorentz case. I have given a more detailed answer on a very similar subject in my answer to Anirbit: Poincare group vs Galilean group and in the comments therein.