As far as I can tell, it may be better to detail what magic people believe to exist and leave rules in a chapter exclusively for the GM in case he wants to make it real. Bring in the mummies, the solomon's seals, the magic rings, flying carpets, holy grails, the true cross, the arc of the covenant, traditional Jewish golems, etc. If not in functioning mechanics, these things (some of them) should exist at least in rumors.
"Magic" does not have to directly imply the existence of "spellcasters." If you do include spellcasters... Prophets would abound, but only NPCs maddened by the whispering of the djinn, so even if you believe in their magic, there's the possibility they're just plain being lied to. For more traditional spellcasters, look to the Magi, specifically good if you want to tie it to pre-Islamic religions like Zoroastrianism, or to the Sufi (although I don't know when they got their start). Still, you tie it too closely to actual real world religion, you run the risk of losing that psychotic sorcerer archetype that just plain needs to be there if there are spellcasters at all.