This (vacuum fluctuation) energy will produce virtual-particle (VP) pairs and not just electrons as has been mentioned so far. The VP pair is produced by "borrowed" energy from the BH. The Heisenberg uncertainty principle allows for two things here. (1) It allows the VP pair to exist on borrowed energy for a finite, but very short, period of time, and (2) it allows the VP pair to be of any energy amount as long as, again, anything borrowed is returned. Therefore, the VP pair is not limited to just electrons and positrons being discussed so far, it can also be quarks, protons, neutrons, and certain mesons regardless of energy required to produce the pair.
So, one of the "virtual" particles falls back into the BH and the other becomes a "real" particle with real mass. If it escapes into space (sometimes both will fall back in), then the mass of whatever the escaping particle was will exactly match the mass-loss of the BH. Mass is delivered into the realm of real and the BH loses that much mass, so the first two laws of thermodynamics are still happy, nothing has been violated.
How does a small BH become so hot and evaporate so fast? Well, the "standard" HR process just mentioned was about one, single VP pair. In a large BH idling along this might be the case here and there around the EH. But, in a smaller BH with more energy per squareanymeasure will be producing VP pairs, of many different particle types, at a great pace. Now we have a swarm of real particles buzzing all around the EH at a very high density. Some will combine into more complex particles, but most will just escape or, to produce the intense energies mentioned, many particle-antiparticle pairs will meet and annihilate into pure energy. If the density is high enough and the particles massive enough, you will see the gamma-ray production Chronos mentioned, again, especially from small, short-lived BH's. Of course, it is actually the entire EM spectrum of photons, and many particles, that are produced but the gamma rays get the most attention.