Both "sooner or later" and "soon or late" appear in English writing from a fairly early date. Here is the Ngram chart for "sooner or later" (blue line) versus "soon or late" (red line) versus "soon or later" (green line) for the period 1500–2000:
Not all of these instances use the wording as a set phrase meaning "eventually"—but many of them do.
'Soon or late'
One earliest instances of "soon or late" that a Google Books search finds is from Nicolas Talon, The Holy History (1653, translated by the Marquess of Winchester):
However it be, divine Wisdome is a Sun which is alwaies in his high-Noons,and at the same instant inlightens the evening and morning, that is to say, the future and past time, as well as the present. These wayes though oblique goe alwaies straight, and soon or late bring us to the Haven.
The instance of "soon or late" here is clearly the same as the familiar "sooner or later"—that is, the implication is not that the divine Wisdom sometimes brings us to the Haven too soon or too late, but rather that it does so eventually. The book includes twelve other instances of the same phrase:
"and either, soon, or late, some chast Sara must be taken away";
"those goods which either soon or late we must leave";
"and either soon or late this thunderbolt must rend the Clouds";
"soon or late we shall be freed of them";
"but soon or late thou shalt confesse that innocence an truth are too dear unto God";
"soon or late thou wilt land in the fortunate Iland";
"we must quit all we have, or else either soon or late, be forsaken by them";
"those wicked souls, who soon or late publickly break their vowes";
"all Divine Lawes are either soon or late are violated";
"and who is wont, either soon or late, to punish all those that prove rebellious";
"let us hope that either soon or late these curtains, Veils, and Clouds, will be withdrawn";
"yet they will either soon or late lose their lustre."
Eight of these dozen instances use the wording "either soon or late," which may sound especially archaic to modern ears. Still, we could replace the expression "soon or late" or "either soon or late" in each case with "sooner or later" with no injury to sense.
Likewise, "The Bill, Entituled, An Act for Preventing Occasional Conformity" (February 13, 1691) has this:
There are some necessary Charges incumbent on the King in the Administration of the Government, which these Supplies are to defray ; there is no Fund set aside for Contingencies, no Provision made for Casual and Incident Charges, but all Extraordinary Expences require an Extraordinary Supply ; and, when the Commons do think fit to erect such a Commission, the Expence made in the Execution of it must, soon or late, be drawn from the Purse of the People ; and since the Burden must inevitably light upon their Shoulders, they only can be Judges of the Weight which is fit to be imposed; and to assign the Quantum of the Charge; which in this Case is proportionable to the Number of the Commissioners ; ...
Owen Feltham, Resolves: Divine, Moral, Political (1696) uses "soon or late" in a way somewhat less interchangeable with "sooner or later":
Who can say, he can travel in safety when his way is in a Forest of Wild Beasts, Thieves and Outlaws ; when man is his own Syren, and when in all the streams he swims in, Baits are strewed? Death to a Righteous man, whether it come soon or late, is the beginning of a certain happiness; the end but of a doubtful and allayed pleasure.
Many of the early instances of "soon or late" appear in poetry, where the demands of poesy led to a Procrustean shortening of the metrical feet from "sooner or later" to "soon or late," with no intended alteration in meaning. But the phrase also appears occasionally in prose under no such compulsion. For example, from the anonymous pamphlet, "Hell upon Earth: or, The Town in an Uproar" (1729):
The Monies being divided, and proper Instruments in Law sign'd and seal'd, the next took into Consideration the untain and' Transitory State of the Things of this Life, and knowing that Papers as well as Men are mortal, and must soon or late die, they therefore order'd the Printing of their Paper to be immediately perform'd near Exeter Exchange in the Strand, to the End the worshipful and worthy Company of Upholders might be at Hand to decently inter it, in Case of such an Accident.
The word untain in this excerpt is unknown to me; it may be a printer's error for uncertain.
'Sooner or later'
A Google Books search turns up instances of "sooner or later" from as early as 1600. From Henry Cuffe, The Differences of the Ages of Mans Life (1600):
For Gods power hath a two-fold consideration, the one absolute, without regard of any his decrees whatsoeuer, whereby he is able to do all, euen those things, that he will not; the other conditionall, ioined with the consideration and respect of his will, whereby he is able to doe all things which hee will, and onely thoe things which he will. God therefore, respected without his decree, was able, sooner or later to create the world; but if we consider him together with his purpose, hee could not either haue preuented, or deferred this his intended worke of the creation: ...
The first moneth is allotted vnto Saturne: the second vnto Iupiter, and so foorth in order, vntill they haue all finished their dominion, and then they begin againe: which is the especiall reason alleaged by some, why the childe that is borne in the eight moneth, for the most part dieth, when as oftentimes those that are brought foorth a moneth sooner or later, liue in verie good health: for Saturne is a planet whose influence causeth colde and drinesse, which both are qualities enemies vnto life.
The first of these two instances, it seems to me, uses "sooner or later" as a set phrase with the meaning "eventually"; the second, however, uses it in the sense of "before or after"—that is, not as a set phrase at all.
From John Dod, A Plaine and Familiar Exposition of the Ten Commandments (1604/1622):
The second duty to be performed to their children, when they be more growne in yeares, is to prouide for the disposing of them in marriage, and that in seasonable and due time, according to the necessity and naturall inclination of their children, sooner or later.
This instance is almost perfectly ambiguous: it might mean "sooner if that suits, or later if that does"; or it might mean "eventually." I lean toward the first interpretation, but both meanings were already in use and neither would be out of place in the context of Dod's disquisition.
And from "The Life of S. Elzear, Count of Sabran" (1638) [combined snippets]:
If your house be filled with goods of the Church il gotten, & as il possessed by such as haue no title ; rest assured, sooner or later it wil ruine your house, and bring vpon you one after an other so many miseries, that you wil curse the time of them : But Alas, Perhaps it wil be too late; ...
I wil know the Virgin state is the most perfect, but your quality permitteth it not either in a Cloister, or the world much lesse among Court-Coles, where you shal & none of those Phenixes ( which sooner or later are not there consumed to ashes. If you haue made some indiscreet Vow , we haue Iudgment enough to discouer it, and power to absolue you of it, and rather then faile the King of Sicily hath sufficient credit to procure his Holines to giue dispensation.
'Soon or later'
Although "soon or later" might seem a handy compromise between the first two alternatives discussed here, writers have warmed to it very little and it is quite rare. The earliest Google Books match for this phrase is from a poem, where it appears to owe its existence to the exigencies of both meter and rhyme. From Hymn 170 in A Collection of Hymns of the Children of God in All Ages, from the Beginning till Now (1754):
Till once into his Arms,
Ev'n as my soul's Creator,
(Who from all casual harms
Restores us soon or later)
I shall with rapture run;
I have this Plea to shew.
That he with me in one
Did in Pain's furnace flow.
A casual examination of Google Books search results reveals instances of "sooner or later" as a set phrase meaning "eventually" from 1600 onward, instances of "soon or late" in the same sense from 1653, and instances of "soon or later" in the same sense from 1754 onward.
The odd thing about "sooner or later" as a set phrase is that it doesn't complete the temporal comparison that it begins so vigorously: sooner or later than what? a person may wonder. But the answer seems to be "sooner or later than the time set down as some instance-specific expectation or other reference point." At least in English, the very indefiniteness of the expression seems to have worked in its favor—as its popularity relative to "soon or late" suggests.
And it isn't as though no one ever thought of using "soon or late" as an alternative form with essentially the same idiomatic meaning. "Soon or late" in the sense of "eventually" has appeared in print for at least 364 years—and yet it shows no signs of stealing the affections of English speakers from "sooner or later." Given the choice, English speakers seem to prefer "sooner or later."