I feel you may be underselling the religious source of law in medieval/renaissance Europe (or I am underselling how you put it in the global story?). Saint Augustine argued for the concept of Just War, with Saint Thomas Aquinas putting it on firmer footing. This is a very clear expression of the idea that a sovereign decision (going to war) is strictly limited by, essentially, Divine law - and Augustine can't have borrowed it from the Islamic principle yet.
Going back further, it is also a core message (but apparently not active practice) of the Old Testament: when rulers rule according to the rule of (God's) law, they and Israel prosper; when the rulers flaunt the rule of (God's) law, Israel suffers and prophets loudly declare such is the case.
No, I am actually talking about actual laws of man, i.e. implemented by magistrates and judges in human courts, not abstract natural laws or concepts of justice. "Just War" is fine, but you're not going to get a judge to issue an arrest warrant on that basis. Judges in Western countries depend on the crown and implement the laws of the crown, not the laws of God.
Islamic law - Shari'a - are actual laws, implemented here on earth. Human judges issue judgments, arrest warrants and sentences based strictly on the Sacred Law, which comes out of the Qur'an and the Sunnah, or are derived from them by very strict rules of jurisprudence. Just like laws in Puritan states were taken straight out of the Bible. Legislation does not come from rulers, kings or assemblies, sultans or shuras. God and only God legislates. Or as Puritans liked to put it, the only king is King Jesus. The monarch cannot make laws, but is bound to uphold to the Sacred Law and only that. And should he interfere or "innovate" (a grievous accusation) and propose new laws, he is instantly deposed. The law of the land is entirely in the hand of jurists and religious scholars who interpret the Sacred Law, and nothing is in the hand of kings or parliaments.
That's "rule of law" in its purest sense. Law is entirely independent and above rulers.
Yes, that is consonant with the organization of the Ancient Israelites - which should be no surprise, as the Hebrew Bible is where both Muslims and Puritans take their cues for social, political and juridical organization, as well as their laws. But you don't need to wait for Elijah to complain and hope the king has a change a heart. In nomocratic states, jurists, on their own, can declare a king deposed. And pretty easily - just drop his name from Friday's prayers.
Of course, it helps that the Sacred Law is written. And while Jews, Muslims and Christians have written holy scripture, not all others do, and so are at a distinct disadvantage. Most Pagan states did not have written scriptures and had to construct a body. Which is why Roman law is built on the edicts of emperors, and Germanic law on the edicts of kings. And "Western law" emanates from that, from royal edicts, not from the Hebrew Bible. You cannot instantly invalidate a parliamentary act by citing chapter and verse from Deutoronomy, or pass a sentence based on it.
The Chinese, of course, have scripture. As do Hindus. Even though Western historians for a long time did not realize that, and so came up with "oriental despotism" nonsense to explain what was going on. Heck, some historians even extended that to Islamic rulers, the most nomocratic of nomocracies, proof positive they had not the faintest idea of what they're talking about.
I notice that there's a vast gray area between the message that rule of law ought to be, and that rule of law is, and so maybe that's what you're primarily talking about, but I don't know enough about the Chinese case to know if they also had the message (ought to be) while not usually having the fact (which is how I would interpret most history of post-Roman Europe - everyone knew there should be rules rulers respect, but only after '1789' did it become persistent active practice in many countries, though there were long-since areas of operation where 'traditional' rules could not realistically be superceded - and the presence of such helped herd trade to some countries and not others).
The practice of 1789 - at least its immediate aftermath - was to let the "Will of the People" be the new despot (Article 6 of the Declaration of the Rights of Man). The arbitrariness of royal edicts morphed into arbitrary acts of the assembly or plebiscites. The rule of law was no stronger after than it was before.
It took a much longer process - certainly in Continental Europe - to get to what you might recognize as a relatively independent judiciary - that is where a judge can interpret and decide the law. And even so, not without some significant slips and backsliding.
It was not Enlightenment thinkers that came up with the concept of an "independent judiciary". It was a concept associated with religious Puritans. Indeed, you would be hard-pressed to find a (non-puritan) Enlightenment thinker in the 18th C. who ever dreamed of it. It emerged only through the 19th Century. And was quite by accident.
I will grant one thing to 1789 - the constitutional endowment of legislative power to parliament, the very statement that "law is the will of the people", did have an inadvertent effect in this process. Because for all revolutionary joys, everyone in Western Europe, even through the 19th C., agreed with the Medieval notion that justice was the exclusive prerogative of the the king. The judiciary was part of the crown, justice was "the king's justice", the courts belonged to the crown and not to "the people", judges were royal appointees, not appointees of parliament nor elected.
This post-1789 assumption - parliament makes the laws, king makes the justice - creates a gap between legislation and judiciary functions, a separation no Enlightenment thinker really thought about. And it is through this little gap that the modern independent judiciary slipped through. Because now the king's judge - a judge that belongs to crown not parliament - gets to interpret and decide the law on his own, independently of the lawmakers.
It is here where the old Puritan notion is revived - the kig does not legislate, law "comes from elsewhere" - not God exactly, but still from somewhere else. And so the judge has a new interpretative function at the center of his duties ("The law is written. What does it mean?"), much like any Islamic
qadi of old.
So all that we associate with "rule of law" today (e.g. judicial review, etc.) comes out of this accident. It is old hat for Puritans, but new hat for everyone else. It was legal philosophers in the course of the 19th C. (not 18th C.) that had to come to terms with this strange new phenomena of an independent judge, and revising - philosophically and practically - the rules of jurisprudence to accommodate it.