Allmusic.com says MEDINA was written by Martin Cradick and Outback. Martin Cradick is a member of Outback. The tune appears on Outback's album "Dance the Devil Away" (1991).

I listened to a sound sample, and the tune definitely sounds middle-eastern, but I don't know whether it's totally new, or based on some traditional tune.

There are several other songs or tunes called MEDINA listed at Allmusic.com. I've listened to a few of them, but they don't seem related.