The song relies on a general Cold War amusement at all things that sounded strange and Russian (as in the Rocky and Bullwinkle cartoons, or some of the James Bond villains), and the exaggeration of many common stereotypes and tropes connected to the USSR and Russia. Mathematics was one of the main things the Western public associated with Soviet Russia in the post-Sputnik era (edit: see comment below), so the choice of a mathematician as the protagonist is natural.
Lehrer was also a mathematics Ph.D student. The basic outline of the Gauss-Lobachevsky-Bolyai historical episode is famous enough in mathematical circles that Lehrer knew it would generate some additional humorous associations when combined with the "plagiarize!" motif. Given this and the Danny Kaye routine, putting the ideas together must have been quite natural for Lehrer, especially with Nikolai Ivanovich Lobachevsky being a suitably long name (by US standards) to pronounce multiple times in the song.
If one were writing a parody involving Shakespeare then a comparable line would be "steal from Marlowe!" (or Bacon, or Burbage, or another of the famous hypothetical authors), and given the comedic license it would not be interpreted as a serious statement about the origin of the Shakespeare plays.