AIUI, in Arabic, a person’s title will often add an “al-” at the beginning and an “i” at the end to denote where that person is from - i.e., the ISIS leader Abu Bakr al-Baghdadi was from Baghdad, so, “al-Baghdadi,” and Saddam Hussein was born in Tikrit, so he was called “al-Tikriti.”
What if the person’s birthplace is from a city ending in a vowel, such as Mecca or Medina? Is it “al-Meccai,” “al-Meccayi?”
No, it’s “al-Makki”, “al-Medini”, etc.
And such a toponym-derived nisbah isn’t necessarily the birthplace of the individual: it could be effectively a family surname first bestowed on some ancestor who happened to be from that place, and then preserved by descendants who may never even have been there. Like Dutch or German names such as “van Rijn” or “von Ingersleben” shared by numerous people who’ve never seen the Rhine, or Ingersleben, or wherever they are nominally “from”.
Much thanks!!
`Afwan! 
Or just made up like none other than Abu Bakr al-Baghdadi, who is NOT from Baghdad, and whose birth name is: Ibrahim Awad Ibrahim al-Badri.
Um, yeah, sure, any Arabic name, with or without a nisbah, can be a made-up name, just as any other kind of name can be a made-up name.
“Abu Bakr al-Baghdadi” is indeed a pseudonym or nom de guerre rather than a birth name, just like “Mark Twain” and “John Wayne” and “Butch Cassidy”.
But this is pretty much irrelevant to the OP’s question. There’s nothing about a toponym-derived nisbah like “al-Baghdadi”, “al-Madini”, etc., that makes it any more likely to be pseudonymic than any other type of name.