This is partly a repetition of the argument presented in an earlier question of yours and in the chat therein.
Lagrangians are an exercise in repetition. You cannot derive a Lagrangian per se. You already have to know the answer.
step 1:
You start with the equations of motion of a system (be electrodynamics, classical mechanics, QED etc.) that you know from other methods.
step 2:
You know the Euler-Lagrange equation, that needs a Lagrangian $\mathcal{L}$ as input and that gives the equation of motion as output: $$ \frac{\partial\mathcal{L}}{\partial q} - \frac{\mathrm{d}}{\mathrm{d}t}\left (\frac{\partial \mathcal{L}}{\partial \dot{q}}\right ) = 0, $$where $q$ is your variable of choice (e.g. position $x$), and $p = \partial \mathcal{L}/\partial \dot{q}$ is the conjugate momentum.
step 3:
You invent a Lagrangian $\mathcal{L}$ that, when put into E-L, gives you back your equation of motion.
step 4: So what's the point of re-writing known equations of motion in Lagrangian formalism? It's more compact, it's a scalar (does not require immediate choice of basis), it's more elegant, manifestly symmetric, easier to implement constraints.
In your specific case at hand, relativistic mechanics.
You already know that the momentum $\mathbf{p}$ is given by:
$$ \mathbf{p} = \gamma_{\mathbf{u}} m_0 \mathbf{u}, $$ where $m_0$ is the rest mass and $\gamma_{\mathbf{u}} = 1/\sqrt{1-u^2/c^2}$, and the energy $E$ (or the Hamiltonian $H$, same thing) is given by:
$$ E = H = \gamma_{\mathbf{u}}m_0 c^2. $$
Then you make stuff up until you notice that this specific choice:
$$ \mathcal{L} = -\frac{m_0 c^2}{\gamma_{\mathbf{u}}}$$ gives you the correct answers.
Specifically:
- momentum: $$ \mathbf{p} = \frac{\partial \mathcal{L}}{\partial \dot{\mathbf{r}}} = \frac{\partial \mathcal{L}}{\partial \mathbf{u}} = \gamma_{\mathbf{u}}m_0 \mathbf{u},$$
and
- energy: $$ H = \mathbf{p}\cdot \dot{\mathbf{r}} - \mathcal{L} = \gamma_{\mathbf{u}}m_0 c^2.$$
In all of the above I assumed zero external potential(s) $V(\mathbf{r}, \dot{\mathbf{r}})$.
EDIT
The OP seems to be wanting a "proof" for his factor of $\epsilon$.
So let's do that.
Let's "guess" a lagrangian of the form: $\mathcal{L} = \epsilon / \gamma_{\mathbf{u}} = \epsilon \sqrt{1-\frac{u^2}{c^2}}$ like in your question.
Let's calculate $\left (\frac{\partial \mathcal{L}}{\partial \dot{x}}\right ) = \left (\frac{\partial \mathcal{L}}{\partial u_x}\right ) = -\epsilon\frac{u_x/c^2}{\sqrt{1-u_x^2/c^2}} = -\epsilon \gamma u_x/c^2$. Where I'm doing it in 1D for clarity.
This has to be equal to the momentum $p_x = \gamma m_0 u_x$, because we know it from relativistic mechanics.
Equate the two: $$-\epsilon \gamma u_x/c^2 = \gamma m_0 u_x \quad \Rightarrow \quad \epsilon = -m_0 c^2 !$$
