Yemen would be after Mecca of course though the OTL Mongols did leave unscathed Shia Holy sites such as Najaf and Karbala unscathed, while Qom was shortly rebuilt after being destroyed by the Mongols. Doubt the razing of Mecca and Medina would destroy Islam or prompt that hysteric a reaction (from reading other threads on here exploring similar themes) though such an event at the hands of the Mongols would definitely dampen the religious triumphalism in the long term unlike OTL Qarmatians, perhaps even spawn an Islamic equivalent of Augustine of Hippo's The City of God as well as potentially provide a catalyst for change.
It would interesting seeing the Mongols somehow managing to cross the Bab-el-Mandab from Yemen to Djibouti / Eritrea towards Egypt from the south tearing through Khartoum along the way though doubt it is plausible.