It doesn't seem likely that a mutually beneficial relationship between the Mongols and the Byzantines could persist for long. The Byzantines would have a hard time justifying the payment of tribute to the Mongols, as it would clash with the view of the Roman Emperor as the protector of Christians, and the Roman Empire as the full territorial extent of civilization, with everyone outside being a barbarian. Any emperor who decided to stop paying tribute would become immensely popular. However, the Mongols also can't stand one of their vassals disobeying either. Commence a war between the two powers, and one of them exacting tribute from the other until another war starts.
At best I could see a repeat of the Byzantine-Arab wars or Byzantine-Persian wars. A continuous cycle of Empire A exacting tribute from Empire B, sometimes the other way around, until one of the empires destroys themselves. However, between the wars, some beneficial trade goes on.
The justification might make the Emperor unpopular whilst he pays tribute - but whilst the Emperor is both the Enforcer in the area, he'll probably have some strong Mongol backing to keep him in power. But it wouldn't be the first time the Romans have paid tribute to Barbarians, so I think using the parallels of Attila to justify it might well work. Plus, saying that you'll bring Christianity to the Mongols would be a good sell - and considering the partnership and recent successes of the Romans, they may have some success. Christian Mongols would be great! (Even if it is just in Persia).
Regarding stopping tribute, didn't the Russians disobey near the end of the Empire? Assuming that the Romans have the sense (and some level of gratitude), they'll probably wait for a similar moment. After all, under the Mongols rule, the Romans have a secure eastern flank, and can invest in western conquests for the first time in centuries with little to no fear of an invasion from the east.
It may well collapse into that, unless something seriously changes in the demographics of Persia, and the political situation post-Mongols. If say Mesopotamia goes Christian under the Mongols then the frontier of the Roman-Persian wars may shift to the Iranian Plateau, as the Romans step in to protect the Christians in Mesopotamia - or Persia might refocus around Central Asia under Mongol rule (unlikely though). Seeing a rebirth of Zoroastrianism after isolating Persia by land is a fun idea (that is even more unlikely than a Central Asian refocus).
If the only PoD is the Mongols asserting domination over the Byzantine Empire, then I don't see much change immediately. Byzantine Empire will benefit greatly from trade with the Orient. The Mongols' cruelty would make any ruler think twice before considering treachery, though it wouldn't matter much since the Mongols would soon break up.
Byzantium will assume the OTL position of the Ottoman Empire ATL, and greatly changing the path of Europe since eastern goods will still be cheaply available.
And slightly more - as trade with the Byzantines would be seen as preferable for Christians than with Muslims (after all, that is why Venice had the pretext of trading to save artifacts). Without needing that pretext, trade will be MUCH larger - possibly making Egypt and the Empire wealthier than their Ottoman counterparts.
If Muscovy is anything to go they may considering the bloodline of Genghis Khan to be really important and prestigious to marry into, that and the Byzantines would at keep the postal Iam system.
What would the Hellisation of Borjigin look like Borjiginos? Emperor Alexios Borjiginos-Komnenos is a pretty epic name.
The Byzantines already had a horse relay system, the Logothetes tou dromou, inherited from the ancient cursus publicus. This service might have disappeared by the 12th century, but even if it did, the replacement position Tzaousios has been theorized to represent a mounted messenger or courier office. In addition, the ancient Roman roads were maintained up to the 13th century or beyond.
Of course, that doesn't necessarily prevent Mongol-inspired reforms.
What would these look like? I'm not entirely aware of a significant difference between the two.
Recognising now that you meant 1204 rather than 124, I think the marriage idea is quite plausible.
It didn't take long for scholars to attribute mythical Abrahamic status to the mongols, the Shi'ites of Iraq believing Genghis Khan to be a direct descendant of Keturah, one of Abrahams wives/concubines.
Considering the proximity, it wouldn't be over surprising for a surviving Rome to legitimise a marriage alliance in such a fashion.
I refer you to the Emperor, Vice Gerent of Christ and Descendent of the Great Khan, Alexios Borjiginos-Komnenos, true and proper Emperor of the Romans, and the most Christian Ilkhan.
