How does potential energy increase without increasing matter?

"I increase its mass according to special relativity." This statement is incorrect. $E^2 = (mc^2)^2 + (pc)^2$ where $p$ is the momentum of the particles, say nothing about the potential energy.

This equation is about ONE particle which is moving at constant speed. on the other hand spring is made of many many particles which are attached to each other via electromagnetic force and is almost at rest.

Putting it all together, when you compress a spring because you only increase the potential energy and the spring is still at rest.

When you compress a spring, the position of the atoms are changes a little bit and when you let the spring go, the atoms want to go back to their original positions because of inter-molecular structure.

Final note, you can never increase the rest mass of a particle.

And that is why

$$ E = mc^2 $$

is remarkable. While there are particles with mass in the spring, the total mass of the spring is not sum of the masses of its parts, it includes stored potential energy and (negative) binding energy of the metal lattice/plastic polymers (divided by $c^2$).

What makes "matter" as we know it special are conserved quantum numbers. It may sound a bit silly, but quantum field theories of these thing involve conserved baryon number and approximately conserved lepton number.

Baryon number conservation means the total number of protons plus neutron (minus the number of antiprotons and antineutrons) remains constant. Lepton number is a bit more tricky thanks to neutrinos, but in this instance, it means the total number of electrons (minus the number of positrons) remains constant.

On the outside chance your steel is contaminated with Co-60, then it will emit some beta-rays (electrons), but their "lepton number" will accounted for by the production of an anti-electron neutrino, which will escape its Earthly confines.

BTW: 99% of the proton and neutron mass is from binding. The quark masses only contributed about 1%.

Anyway, in summary: mass is mostly not conserved matter. It is predominately energy, and it can be moved around in both chemical and nuclear reactions. What we casually think of as "conserved matter" comprises particles with conserved additive "numbers" (and subtractive numbers for antimatter, in fact the biggest distinction between matter and antimatter is the sign of its appropriate conserved quantum number, beyond that they are remarkably similar).

The "stuff" that "goes" to the spring is this quantity:

$$V=frac{1}{2}k(x-x_0)^2$$

That is all. It is not "stuff", it is just a quantity.

The interesting thing about this particular quantity is that it is one term in energy conservation law, that can be understood more deeply through Noether theorem and symmetries of physical laws.

In physics, one looks at things operationally, just like in mathematics. Mathematician will not tell you what natural number really is, but he will go in great lengths to tell you how it behaves and how it relates to other things in math.

Science is the same. We do not see the inner nature of things in our experiments and observations, we only see how they behave and how they relate to each other. Thus, if we are to be perfectly honest with ourselves, we cannot claim more knowledge than this.

But mass is supposed to be a measure of the quantity of matter, isn't it?

No, not in relativistic physics or in quantum physics. For example, most of the apparent mass of a proton or a neutron comes from the binding energy of the strong nuclear force that binds its three constituent quarks together. The rest mass of the quarks is only around $1%$ of the apparent mass of the proton or neutron. So most of the apparent mass of all the objects that you see around you comes from this binding energy, rather than from the rest mass of fundamental particles.