Thanks for the additional information.
Despite its disclaimer to the contrary ("Not to be confused with the Dennis Quaid movie/Barry Longyear story Enemy Mine"), I think the TV Tropes article is, in fact, confused with the Dennis Quaid movie/Barry Longyear story Enemy Mine, and the TV Tropes author is interpolating something from the title that is not there.
Although I haven't seen the movie or read the book, there are no indications given in several summaries (Wikipedia for film and book, NYT review of the movie cited in Wikipedia article) as to why the movie is so titled. From the plain words "Enemy Mine", and the general gist of the book (former enemies work together when put in a dangerous situation isolated from the war that made them enemies), it appears that Longyear was trying for a more-interesting version of "My Enemy" by using the archaic "Mine" in lieu of "My" and inverting the words, along the lines of what @Shane wrote in his answer.
I think it is safe to say it is an invention of Longyear, futher popularized by the movie of the same title, which a lazy TV Tropes author tied to an existing proverb because both contain similar words. I do not think that the equivalence between "enemy mine" and the ancient maxim is valid or widespread.