For the most part it's the existence of Latin titular sees in the region. It's not that the Latin forms are constructed, but based off of the actual known Latin forms of the location. At least, from what I've noticed doing some transliteration on my own end.
Once you get outside of the territories of the former Roman Empire, you're going to stop finding actual examples of titles in Latin and are just going to need to transliterate them yourself. Brush up on your Latin word forms, check some examples of other Roman Empire cities named after the name the locals gave the place, open up the
Latin IPA help page on Wikipedia, look up what the locals called the place by the time you get to conquering it, and get cracking.
