If you go all the way back to the derivation of the Lagrangian, I think you can see why the relativistic Lagrangian is what it is. Usually, one starts with d'Alembert's principle
$$ \sum_i \left(F_i - \dot{p}_i\right) \delta x_i = 0, $$
where $F_i$ are the forces acting on particle $i$, $p_i$ is its momentum, $\delta x_i$ is a virtual displacement, and the dot designates differentiation with respect to coordinate time $t$. For the relativistic case, we use the proper momentum $p = \gamma m v$.
Focusing on the relevant term only:
$$-\dot{p}\, \delta x = -\frac{d(\gamma m v)}{dt}\, \delta x $$
We use the chain rule (or integrate by parts):
$$ = -\frac{d}{dt}\left(\gamma m v\, \delta x\right) + \gamma m v \frac{d(\delta x)}{dt}$$
When we do the full variation the first term vanishes because $\delta x=0$ on the boundary. Under typical assumptions the ordinary and variational derivatives commute:
$$ = \gamma m v\, \delta v$$
We want to end up with a statement like $\delta(\mathrm{stuff})$. If you are smarter than me, you might see that:
\begin{align}
\delta\left(\frac{1}{\gamma}\right) &= \frac{1}{2} \left(1-\frac{v^2}{c^2}\right)^{-1/2} \frac{-2v}{c^2}\,\delta v = -\frac{1}{c^2}\,\gamma v \, \delta v \\
\delta\left(-\frac{mc^2}{\gamma}\right)&= \gamma m v\, \delta v
\end{align}
or you could know the answer and `astutely guess' like I did.
When you go through the whole variational rigmarole you'll end up with something like:
$$ \int_{t_i}^{t_f}\sum_i \left(F_i - \dot{p}_i\right) \delta x_i \,\mathrm{d}t = \delta \int_{t_i}^{t_f}\left(-\sum_i\frac{m_i c^2}{\gamma_i} - V \right)\mathrm{d}t = 0 $$
So for a single particle
$$ L = - \frac{m c^2}{\gamma} - V.$$