Sure, it just takes a while. You can build roads from Marrakesh down to the place where it's possible to cross the Sahara, which makes the crossing easier to find. After that it's just a matter of spending lots of turns sending down an invasion force. Spies are helpful, since the Sahara can get pretty trackless.