Is there a mathematical reason for the Lagrangian to be Lorentz invariant? The Hamiltonian is the energy, which is just one component of a four-vector and therefore not Lorentz invariant. 
The Lagrangian is the Legendre transform of the Hamiltonian and I was wondering if there is some good reason why we get through the Legendre transform something invariant?
 A: The previous answer is very good, but I think can be simplified a bit.
In particle mechanics, the Lagrangian $L$ is 
$$L = p\dot{q} - H$$
So let's look at this in special relativity. We get, with $p = \gamma m v$, $\dot{q} = v$, and $H = E = \gamma mc^{2}$,
$$L = \gamma mv^{2} - \gamma mc^{2} = - \gamma mc^{2}(1 - (v/c)^{2}) = - mc^{2}/\gamma$$
It's not that $L$ is a scalar (which is what I thought originally), but that $\int L\,dt$ is a scalar. And this is easy, because
$$\int L\,dt = -\int (mc^{2}/\gamma)\,dt = - \int mc^{2}\,d\tau$$
where $\tau$ is the proper time. This integral is clearly invariant, as we should wish for the action. 
A: The Lagrangian is what is integrated over spacetime in the action, i.e. has to be a 4-form. As such, it is necessarily a (pseudo-)scalar under Lorentz transformations.
When wondering about Lorentz transformations and such, the Hamiltonian is, as a non-Lorentz-covariant object, not a good starting point, by the way. It is often better to start with the Lagrangian that makes the Lorentz covariance of the theory manifest.
A: We will here give our interpretation of OP's question (v4).


*

*We assume that OP's definition of Lorentz covariance is that the equations of motion (eom) of the theory is Lorentz covariant.

*We will assume that the theory has an action principle, and that the eoms are the Euler-Lagrange (EL) equations.

*One may prove that Lorentz invariance of the action implies Lorentz covariance of the EL eqs., cf. e.g. this Phys.SE post. 

*The implication (3) does in principle not hold in the other direction, but in practice Lorentz covariant EL eqs. arise from a Lorentz invariant action principle.
Putting these facts together show that it is natural to expect that the action to be Lorentz invariant for a Lorentz covariant theory, cf. definition (1).


*Next, we will assume that the Legendre transformation is well-defined. 

*Also we will assume that the Legendre transformation is an involution, i.e. performing the Legendre transformation twice gets us back to the starting point.
In particular, if OP starts from a Lorentz covariant (but not necessarily manifestly$^1$ Lorentz covariant) Hamiltonian formulation, this means that the Hamiltonian eoms are Lorentz covariant, cf. definition (1). 
The Hamiltonian$^2$ $H(q,p)$ itself is of course not Lorentz invariant, but the temporal component of a four-vector, as OP correctly writes. Points 2-4 now motivate that the Hamiltonian action $$S_H[q,p]~=~\int \!dt ~(p_i\dot{q}^i-H(q,p))$$ is Lorentz invariant. It follows that the Lagrangian action $S[q]$ is also Lorentz invariant. 
--
$^1$ For manifestly Lorentz covariant Hamiltonian formulations, see e.g. my Phys.SE answer here.
$^2$ The following argument can be extended to field theory.
