^There were instances of planetary genocide in TOS, such as "Operation: Annihilate!," "The Changeling," and "The Immunity Syndrome." It's just that it was mostly offscreen, a disaster mentioned as already having occurred before the episode began, so the consequences weren't really felt. Or just after the episode, as in "The Empath" -- remember, there were multiple inhabited planets doomed by the supernova and the Vians could only save the population of one of them. So yes, there were billions of lives lost in TOS, just not Federation lives.
Not to mention the huge losses that Starfleet suffered in the second season -- the crews of Constellation, Intrepid, Excalibur, and Exeter all wiped out, plus numerous casualties on Lexington, Hood, and Potemkin. And then the loss of the Defiant just months after that. Starfleet was really hit hard in a short span of time there.