I still don't understand what it means when H-Shem says that Moshe has to release Him. What is it that He is bound by? Did He make an oath to Moshe that He's asking to be released from?
On a theological level Hash-m did not make an oath to Moshe but nevertheless he is "bound" and needs to be released. The idea here is that when a person prays in a certain heartfelt manner and is Moser Nefesh he can in a sense change the mechanics of Hash-m and bring about a different outcome. Just as Choni Ha'Meagel stood in a circle and said he would not leave until rain, and just as Chizkiyahu succeeded in changing his fate with a heartfelt Tefillah (Brachos 10a), Moshe Rabbeinu had the power with his Tefillah to "chain" Hash-m until he cancels his decree.
If Hash-m had made an oath, Moshe would not have been able to cancel it just as happened with the Meraglim. However in any other circumstance, man has the ability to affect Hash-m's decision and even change it. Yitzchak prays opposite his wife and turns around her physical state of infertility and there are many other examples of Tefillah changing a decree.
The idea is that when an important person prays with Mesirus Nefesh he can affect the entire world as the world exists because of the Tzadikim, so their prayers can also affect Hash-m's way of ruling the world.
The Acharonim add that the concept of holding Hash-m's clothes refers to his Midos and Moshe is trying to change Hash-m's Midah of Nekama to another Midah (Tzlach; Rav Elyashiv)