Why should momentum be conserved in special relativity? This is more of a philosophical question than an actual physics question, but I don't see a clear reason why relativistic momentum, or energy for that matter, should be conserved.
The equivalence principle, simply stated, states that the laws of physics are the same in all inertial frames. But what makes a given statement a law of physics?
Why couldn't we simply say that momentum is conserved only for $v\ll c$ ? Is such conservation a result of special relativity or a requirement that we add and use to define momentum in the relativistic setting?
How do we judge whether or not any given statement is a universal law of physics?
 A: The short answer? Because the Lorentz group is a subgroup of the Poincaré group. The latter includes translations.
A: The conservation of momentum can be derived from the invariance of the Lagrangian under spatial translations. This follows from Noether’s theorem, so it applies for special relativity. Furthermore you can use Noether’s theorem to derive the form of relativistic momentum.
Regarding determining if something is a law of physics: that can only be done experimentally. You have to show that a candidate law of physics matches the results of experiments. The postulate of relativity is that such laws will not depend on the reference frame, but that claim can only be validated experimentally.
A: Dale's answer describes nicely where momentum conservation comes from, but I thought it might be useful to emphasize that momentum need not be conserved in a relativistic model, just as it need not be conserved in a non-relativistic model. There's nothing about special (or indeed, general) relativity which requires spatial translation symmetry, and so the Noether current corresponding to that symmetry will generically not be conserved.
As far as we know, when all interactions are taken into account then momentum is a conserved quantity; nevertheless, that is not required by the postulates of special or general relativity, and it does not preclude the use of effective models in which momentum is not conserved (e.g. a particle moving through a background Schwarzschild spacetime in GR).
A: "Physics is the same in all inertial frames."
This is a law of physics because it is what we see when we look at the world we live in.
The basis of any theory of physics is looking at the world around us, and then try to find basic principles that fit with what we see.
Starting with this principle and other basic assumptions, one can prove that energy and momentum are conserved.
