There is an ambiguity as to what is meant by 'energy', 'momentum' and indeed 'mass'. One approach (that OP presumably finds unsatisfying) is to declare $p=\gamma mv$, $E=\gamma m$ where $\gamma = (1-v^2)^{-1/2}$ and thus $E^2-p^2=m^2$ by direct calculation. It then remains to show that these deserve the names we've given them. This involves two steps:
1) Showing that as $v\to 0$ we recover $p=mv$ and $E=\frac{1}{2} mv^2$. In fact we get $E=m+\frac{1}{2} mv^2$ but we can recognise that nothing in Newtonian mechanics precluded this constant since we only ever dealt with energy changes.
2) We need to show $E,p$ are conserved. This is harder and is what the various physical arguments tend to focus on.
A 'high level' way to do this would be the following:
1) Agree on a Lagrangian/Action for the system. In this case we take the proper time along a path to be the action of that path.
2) Show that spacetime translations $x^\mu \mapsto x^\mu + a^\mu$ leave this action invariant (ie shifting a curve doesn't change its arc length). This implies by Noether's theorem a conserved quantity called $P^\mu$.
3) Declare the time part of $P^\mu$ to be called 'energy' and the space part to be called 'momentum'. Declare $P^\mu P_\mu$ to be the mass squared.
4)We are now in the same situation as before, where we need to show these quantities are correct to call by those names. Here, a little classical mechanics comes in helpful since in classical mechanics $E$ is conserved due to time translation and $p$ due to space translation. So these certainly correspond. We're left with masses, however we can write out the mass squared relation as:
$$ E^2 - p^2 = m^2$$
which looks a lot like $\cosh^2 \eta -\sinh^2 \eta = 1^2$ so we further define the variable $\eta$ by $E=m\cosh \eta, p=m\sinh \eta$. Whatever this $\eta$ is, it's true that as $\eta \to 0$ we have:
$$ E \to m(1 + \frac{1}{2}\eta ^2)$$
$$ p \to m\eta $$
all of which looks convincing enough to me to just go ahead and say for small $\eta$, $\eta$ must be the velocity, and this has recovered the usual formulas with $m$ where the mass would be, so this agrees with our intuition of what mass should mean as well.