It appears as though Saruman created two separate kinds of creatures, both Men-orcs and Orc-men. from History of Middle-earth:
It became clear in time that undoubted Men could under the domination of Morgoth or his agents in a few generations be reduced almost to the Orc-level of mind and habits; and then they would or could be made to mate with Orcs, producing new breeds, often larger and more cunning. There is no doubt that long afterwards, in the Third Age, Saruman rediscovered this, or learned of it in lore, and in his lust for mastery committed this, his wickedest deed: the interbreeding of Orcs and Men, producing both Men-orcs large and cunning, and Orc-men treacherous and vile.
History of Middle-earth X Morgoth's Ring Part 5: "Myths Transformed"
Precisely what the difference is is unclear; I imagine that one group are the Uruk-hai, and the other are the "half-orcs" that form part of Saruman's entourage in the Shire, as described by Pippin:
'Well I am staggered!' said Pippin. 'Of all the ends to our journey that is the very last I should have thought of: to have to fight half-orcs and ruffians in the Shire itself - to rescue Lotho Pimple!'
Return of the King Book VI Chapter 8: "The Scouring of the Shire"
However which one is which, I couldn't begin to say.
There is precedent for Sauron's army having something similar to the Uruk-hai, although, given how early they appear, they must be distinct from Saruman's Orc-men and Men-orcs. Appendix A tells that an unusually large race of orcs, called uruks (confusingly, the word for "orc" in the Black Speech), appeared in T.A. 2475:
In the last years of Denethor I the race of uruks, black orcs of great strength, first appeared out of Mordor, and in 2475 they swept across Ithilien and took Osgiliath.
Return of the King Appendix A "Annals of the Kings and Rulers" Chapter I "The Númenórean Kings" (iv) Gondor and the Heirs of Anárion
And these uruks remain in Sauron's army right to the end:
The leading orcs came loping along, panting, holding their heads down. They were a gang of the smaller breeds being driven unwilling to their Dark Lord’s wars; all they cared for was to get the march over and escape the whip. Beside them, running up and down the line, went two of the large fierce uruks, cracking lashes and shouting.
Return of the King Book VI Chapter 2: "The Land of Shadow"
Where these uruks came from is unclear. They evidently arose out of Mordor, but whether they were bred by Sauron (and, if so, by what means) or if they evolved naturally is unknown; I can find nothing in History of Middle-earth to clarify.
The first quote in this answer suggests that Morgoth experimented with crossing Orcs and Men in the First Age (note Tolkien says that Saruman rediscovered the skill); this could be a plausible origin for the uruks, but doesn't mesh with the fact earlier stated, that they came out of Mordor in the Third Age.
Unfortunately, we don't know any more than that.