Do not be misled: “Bad company corrupts good character.” Come back to your senses as you ought, and stop sinning; for there are some who are ignorant of God—I say this to your shame. [NIV]
'Bad company corrupts good character' is widely regarded from very early as a quotation. It actually is a good iambic line in the Greek, and so is exactly the sort of thing you would expect to find in a Greek tragedy or comedy.
In his Ecclesiastical History, from the fifth century, Socrates Scholasticus claims that it is a quotation of Euripides. In context (Book III, Chapter 16), Socrates is talking about our very subject, Paul's quotations from Greek pagan literature:
Should any one imagine that in making these assertions we wrest the Scriptures from their legitimate construction, let it be remembered that the Apostle not only does not forbid our being instructed in Greek learning, but that he himself seems by no means to have neglected it, inasmuch as he knows many of the sayings of the Greeks. Whence did he get the saying, ‘The Cretans are always liars, evil beasts, slow-bellies,’ but from a perusal of The Oracles of Epimenides, the Cretan Initiator? Or how would he have known this, ‘For we are also his offspring,’ had he not been acquainted with The Phenomena of Aratus the astronomer? Again this sentence, ‘Evil communications corrupt good manners,’ is a sufficient proof that he was conversant with the tragedies of Euripides.
Unfortunately, the line doesn't occur in any extant play by Euripides. It's worth keeping in mind that this doesn't mean much. We only have at most 19 complete plays out of an oeuvre that may have originally had as many as 90, and the ones we had are a bit of an odd selection, since we get them from one anthology of ten plays that was probably used in schools and one surviving volume of a larger alphabetical collection of his plays (which is why so many of the titles of Euripides' extant plays start with H or I), somewhat as if we were trying to reconstruct Shakespeare from a school textbook and volume 3 of an alphabetical collected works. There's lots of room for the line being in one of the many lost plays.
Socrates seems to be the only person to attribute the line to the tragedies of Euripides. The most common attribution is to the comedies of Menander. This attribution appears to be due to Jerome in his Commentary on Titus (chapter 1), although some others also mention it; unfortunately, I have neither a hardcopy nor an online version of this work, so I only know this through a secondary source. Unfortunately, we don't have any extant play be Menander in which the line occurs, either; we only have one complete Menander play and a lot of fragments.
It is possible that, if Menander has the line, that he was quoting Euripides; there are known cases of him having quoted Euripides elsewhere. If that's so, though, we have no way whatsoever of knowing whether Paul was quoting Menander or Euripides -- beyond the bare antecedent probability that it seems more likely that he would be quoting a tragedy, with its high moral tone, than a comedy, particularly in the middle of a serious admonition. On the other hand, Justin Martyr can be found less than a century later either quoting or alluding in a favorable way to Menander on another topic (First Apology, Chapter XX), and the same can be said for Clement of Alexandria, who refers to him a fair amount, so even that doesn't seem to weigh all that much.
So tragic Euripides or comic Menander? We don't know, although the evidence is reasonably good that he's quoting one or the other.
It has also been suggested that Menander is being quoted or paraphrased in I Timothy 1:15 and 4:9:
Here is a trustworthy saying that deserves full acceptance: Christ Jesus came into the world to save sinners—of whom I am the worst. [NIV]
For physical training is of some value, but godliness has value for all things, holding promise for both the present life and the life to come. This is a trustworthy saying that deserves full acceptance. [NIV]
'This is a trustworthy saying that deserves full acceptance' has some similarities to a comment in a play by Terence, Adelphoi, which heavily adapts from Menander. But, of course, it's also possible that this is just coincidental, or that the phrase just became a common phrase in some quarters, and thus is not a quotation at all.