After discussing with some people, it appears to me that the way to define quantities like "energy" and "momentum" in general, is to just treat them as "conserved quantities" under some special conditions. The original definitions like "product of mass and velocity" and "capacity to do work" ... work well in most cases, but it's clear that as general definitions these are inappropriate.
In that light, it made sense to me to redefine momentum. By using a simple argument. We analyze the elastic collision between two balls in two frames: the rest frame, and the frame of the two balls. It was clear that the momentum, if we just defined it as $mv$, would not be conserved in both the frames.
It made total sense to therefore redefine the momentum. We have: $$\mathbf{p}= \gamma(v) m \mathbf{v}$$ It can be shown that this definition makes it a conserved quantity under no force in both frames, and thus adheres to the principle of relativity.
Now, coming to energy:
It can be shown that (using the newly defined definition of momentum), that the appropriate KE should be: $$\mathrm{KE}= \gamma mc^2- mc^2$$
Now textbooks simply move $mc^2$ to the other side, and then claim that "$\mathrm{KE}+mc^2$ defines the total energy", so we get $E=\gamma mc^2$.
My issue with all of this is again, how should one precisely define energy? Why was $\mathrm{KE}+mc^2$ chosen as the definition of total energy $E$? Is it because, as I said before, it can be shown to be a conserved quantity under some conditions?
Also, why was there a need to consider $mc^2$ as an extra bit of energy in that equation? It appears to me that we can make do of just using the newly defined $\mathrm{KE}$ all the time in energy conservation equations and that shall work too...
