In his violent campaigns for Sulla, it seems Pompey earned himself the nickname Adulscentulus Carnifex or ‘Teenage Butcher’. However I'm not sure which Roman writer first referred to him in this way. So what is the primary source for his nickname?
The main source, and the first mention of the nickname that I could find, is Valerius Maximus' FACTORVM ET DICTORVM MEMORABILIVM LIBRI NOVEM, Book 6, Chapter 2.8.
It is essentially a short story where an accuser from the underworld recounts some of the deaths for which Pompey was viewed as being responsible.
English Translation| Google Books
Latin| The Latin Library