Hello Basil, Salam 3alaikom from Bahrain
kaif al7al?
About the songs you mentioned, I can tell you they are all mostly very old Jewish (Hebrew) poems, written by Rabbis centuries ago, the band however composed the music and instrumentation that is accompanied with the song. That's why different versions of for example "Shir Hama'Alot" will sound different depending on the composer, but the lyrics will still be the same.
An Israeli guy once told me that the intro part of Aldiar Al Mukadasa (where they say ya 7abeeby) is an old jewish prayer in wich people sang when they wanted to return to Israel, back when they were in exile, so yeah that maybe it, the outro of the song however is Arabic (where they say bellah 3alayna kollena).
Elmeod Na'ala is also a hebrew prayer, but it's composed using an entirely Arabic scale "maqam al bayat" (which is common in oriental jewish music).
The outro of Be Thy Father I pray is a traditional and very common arabic/middle eastern melody which can be heard in many songs and tunes, it's not necesserly taken or coverd from a song.
Norra El Norra as we all know already was influenced from old egyptian song Samra Ya Samra.
As'alk and Sapari are both old yemenite poems written by Rabbi Shalom Shabazi سالم الشبزي of yemen, the orignal composition I think (according to Ofra Haza's album booklet) is written by great yemenite singer Aharon Amram, who has his own versions of these songs. There are many variations of the song you can find on youtube by yemenite singers such as Ofra Haza, Shlomit Levi, Aharon Amram, Daklon, Shoshana Damari, Shalom Sabari, Zion Golan and so on.
Olat Hat'mid is another poem written by an old Israeli peot Sa'adia something, I think you can hear what may appear as the orignal song in the start/intro of the track, but then that might be composed/played by the band as well, Dunno.
Hope that helped.
EDIT: oh and btw, at the end of Kiss of Babylon there's another yemenite folk song sang by Shlomit, it's called Ahavat Hadasa.