According to Pliny's natural history, in discussing the origin of magic in the world he mentions Jannes in relation to Moses.
There is another sect, also, of adepts in the magic art, who derive their origin from Moses, Jannes, and Lotapea,Jews by birth, but many thousand years posterior to Zoroaster: and as much more recent, again, is the branch of magic cultivated in Cyprus.In the time, too, of Alexander the Great, this profession received no small accession to its credit from the influence of a second Osthanes, who had the honour of accompanying that prince in his expeditions, and who, evidently, beyond all doubt, travelled over every part of the world. (THE NATURAL HISTORY (ENGLISH) Pliny the Elder John Bostock, Editor, p5425)
There is a footnote from the editor beside the word Jannes that says:
Eusebius, in his Prœ paratio Evangeliea, B. ix., states that Jannes and Jambres, or Mambres, were the names of Egyptian writers, who practised Magic, and opposed Moses before Pharaoh.
There may have also been literature within Jewish tradition that maintained the names of the magicians which has since perished:
According to Jewish tradition, Jannes and Jambres (or Mambres) were the chief of the Egyptian magicians who opposed Moses (Ex. 7:11, 22), but they are also called the sons of Balaam, and there is a story that they repented and accompanied the Israelites out of Egypt. On this last tradition was founded an apocryphal book called the ‘Repentance of Jannes and Jambres,’ not now extant, and perhaps it was from this latter that S. Paul derived his information. For further details see Sehürer, Jewish People in the Time of Christ, vol. iii. pp. 149–151 (E.T.). We need not be surprised at S. Paul referring to this apocryphal book for an unimportant detail, just as a Christian preacher might refer to the Ramayana or the Mahabharat for an illustration without thereby implying that he accepted the rest of the poem as true. (THE PASTORAL EPISTLES, ERNEST FAULKNER BROWN)
So the answer to the question seems to be that there was some knowledge and biblical commentary both in Jewish tradition and Gentile history that is now extant. Paul is simply referring to what was commonly understood at the time to be the names of the magicians, or possibly leaders of two schools of magic who assisted the Pharaoh. Judging from the reference from Pliny it was not considered a mere legend and this probably was their actual historical names.