The black hole loses mass in order to generate the Hawking radiation. The energy carried by the radiation is exactly proportional to the mass lost by the black hole according to Einstein's formula E = mc^2
No new mass is brought into the Universe this way.
EDIT:
(Keep in mind the explanation below is not rigorous. As Stephen Hawking himself has said, this is more like a mental model, good enough to visualize things.)
Virtual particles are called virtual because they don't really "exist" in the common sense. They have mass and they have energy. Due to Heisenberg's uncertainty principle, it's okay if particles with a total energy E almost "exist" for a very short while, as long as they return to nothingness afterwards.
The production / destruction of virtual particles could happen all the time, anywhere, not just at the edge of a black hole. This is fine, as long as each particle only seems to "exist" a short time. Conservation of energy is not violated.
However, at the edge of a black hole, something different happens. You have a pair of virtual particles popping up into existence. Soon after, one of the particles is captured by the black hole, while the other particle moves away from it. Since the captured particle is virtual, it doesn't really have mass and/or energy. No new mass is added to the black hole.
Now the two particles cannot re-annihilate each other. So you have one lone particle moving away from the black hole. It's not a virtual particle anymore, it's a real particle. But it has energy and perhaps it has mass also. Where does the energy come from?
The energy required to make the new particle real comes from the gravitational field of the black hole. The black hole is losing mass in order to power the creation of real particles moving away from it.
Again, don't get stuck in details. This is not what really happens. This is more like a metaphor.