The argument is Einstein is a little annoying to read, here's a simpler version (I put it on Wikipedia under mass-energy equivalence a long time ago. It also appears somewhere on Terry Tao's blog, and it's the right way to make the argument).
Consider a mass M which is stationary. It emits two identical pulses of light in opposite directions, each of equal energy E/2. After the emmission it still isn't moving.
Now consider the frame where the mass is moving with velocity v to the right (so the frame is moving to the left compared to the original frame). It emits two pulses of light in opposite direction, but now the light moving to the right is blueshifted and the light moving to the left is redshifted. The frequency shift is by the doppler shift formula, the shift factor is v/c, and the momentum is E/2c. So the right moving light has more momentum by Ev/2c^2 and left moving light has less momentum by Ev/2c^2, so the total momentum of the light is
to the right. This means that the body has it's momentum reduced by this amount, but the velocity didn't change, so the mass went down. The amount of the mass decrease, to conserve momentum, must be so that the new momentum of the body is:
P = (m - E/c^2) v
so the mass is decreased by the outgoing energy. Einstein uses the energy of the body, not the momentum, but Einstein's argument is equivalent to the one above by 4-vector nature of energy momentum. So Einstein's argument is fine, and there should be no controversy.
Let's consider the same experiment using sound in a nonrelativistic theory of a mass in air. A body emits two pulses of sound to the left and to the right with total energy E/2. Now we shift frames to where the body and the air are moving with velocity v. But now we can't conclude anything--- the air is moving, there is no relativity, the background the body is moving in isn't invariant to boosts.
But consider the momentum balance in the moving frame anyway: the sound moving to the right is blueshifted, the sound moving to the left is redshifted by v/c, but there is no imbalance in momentum, because in Galilean transformations, if the momentum of two things is balanced in one frame, it is balanced in every frame.
Einstein's argument requires the principle of relativity, but he used a small v limit where all the equations are nonrelativistic. The only relativistic equation you use in the whole thing is the relation between energy and momentum of light E=pc. That doesn't mean it's a nonrelativistic argument, because the principle of relativity is invoked multiple times, and the only reason the momentum doesn't balance in the moving frame is because the light is relativistic.
I should point out that Einstein already knew about photons, and for sure was considering two photon emission to come up with this. From the photon principle, he knew that frequency and energy have the same transformation. Otherwise it would be harder to know what the change in momentum energy under blueshifting/redshifting will be.