It turns out that, in the early Muslim era, it was formed in a perfectly regular way. In his masterwork, the medieval geographer Al-Maqdisī (d. 991) calls his hometown Bayt al-Maqdis بيت المقدس ("house of holiness"), a title now largely supplanted by al-Quds ("the holy"). It survives to the present in certain religious contexts or as a poetic synonym, not only in Arabic but in Kabyle Berber as well: H. Genevois ("Croyances") notes a traditional popular belief that the souls of the dead gather in Bit Elmeqdes, corresponding exactly to Al-Maqdisī's boast that Jerusalem is "the site of the Day of Judgement, and from it is the Resurrection, and to it is the Gathering" (عرصة القيامة ومنها النشر وإليها الحشر).
A quick search of Alwaraq's heritage library suggests that the shorter name "al-Quds" became popular around the period of the Crusades, when Jerusalem was as much a subject of dispute as now. The earliest attestation I can spot on a cursory search (excluding a work falsely attributed to al-Wāqidī) is a mention by the Andalusi traveller Ibn Jubayr (1185), who notes that "between [Kerak] and al-Quds is a day's march or so, and it is the best location in Palestine" (بينه وبين القدس مسيرة يوم أو اشف قليلاً، وهو سرارة أرض فلسطين). Very likely a longer search would yield slightly older attestations. By the time of the next major Palestinian writer I notice in the collection - Al-Ṣafadī (d. 1363) - al-Quds had clearly become the unmarked term for the town; it recurs constantly in his work.
The name Bayt al-Maqdis was thus replaced in practice by the shorter and catchier name al-Quds a good 800 years ago, yet the corresponding gentilic continues to preserve the older name. Since 1967, the Israeli government has imposed a third name as its official term for the city in Arabic: Ūrshalīm, a transcription of the Syriac name used in Christian liturgical contexts which provoked "furious ridicule" from residents (Segev 2007:492). Since this usage remains entirely unknown to most Arabic speakers, it is unlikely to have much impact on Arabic usage. Yet the timing of the shift from Bayt al-Maqdis to al-Quds reminds us that political upheaval impacts placenames as well as people's lives.