Shir HaMa'alot

שיר המעלות

Psalm 126 is said before Birkat HaMazon when there's no tachanun. Usually sung on Shabbat. I think I've compiled all the well known American Ashkenazi melodies here.

Rosenblatt (but actually Minkowsky)

Composed by Cantor Pinchas Minkowsky (1859-1924), and famously performed by Cantor Yossele Rosenblatt

A candidate for the State of Israel's national anthem that eventually lost to HaTikva. Also attached, excerpts from Chalom Imi, filmed with Rosenblatt in Israel in 1933 shortly before his death.

 

Minkowsky 2

Well known melody. Surprisingly also composed by Cantor Pinchas Minkowsky just like the one above. This is one of those melodies that's so ubiquitous, almost nobody has recorded a nice version of it.

Modzitz (Kaddish)

Rabbi Shaul Yedidya Elazar Taub (Imrei Eish), 1955

Composed by the Modzitzer Rebbe as Kaddish for Yamim Noraim, but it's better known for Shir HaMa'alos.

An orchestra really transforms the song.

Carlebach (Shomrim Hafked)

Shlomo Carlebach, 1974. Well known melody for Shir HaMa'alot but few people know it's a Carlebach tune.

This song was first sung by Reb Shlomo in a wedding that he performed on September 9, 1974 for Avraham Shifrin and Eleonora Poltinnikiova on the Tel Aviv beach at midnight. Here is the full explanation with the words of the song as published in my book on Reb Shlomo in Hebrew: 

השיר שׁוֹמְרִים הַפְקֵד לְעִירְךָ כָּל הַיּוֹם וְכָל הַלַּיְלָה (מתוך הפיוט בהגדה של פסח וַיְהִי בַּחֲצִי הַלַּיְלָה) חובר על-ידי ר' שלמה ב-9 בספטמבר 1974 בחוף תל אביב בזמן שערך את החתונה של אברהם ואלינורה שיפרין. המלים לקוחות מהבית האחרון בפיוט וַיְהִי בַּחֲצִי הַלַּיְלָה בהגדה של פסח, ומתארות את התקווה לעתיד - "תאיר כאור יום חשכת לילה" ורומזות לפסוק עַל חוֹמֹתַיִךְ יְרוּשָׁלִַם הִפְקַדְתִּי שֹׁמְרִים כָּל הַיּוֹם וְכָל הַלַּיְלָה תָּמִיד לֹא יֶחֱשׁוּ - נבואת העתיד של ישעיה ס"ב, ו.

Modzitz

This melody was actually composed to be used for Shir HaMaalot unlike the Modzitz Kaddish above. But most people (myself included) don't know it.

Bonus content: Other songs from Birkat HaMazon.

Harachaman (hu yishlach lanu)

Kol Salonika, 1972 (Baruch Chait) 

http://djsa.dartmouth.edu/tracks/23681

Harachaman starts at 17:06 in the video below.

Harachaman (hu yanchileinu)

The Rabbis' Sons, 1970 (Baruch Chait)

http://djsa.dartmouth.edu/tracks/42561

https://drive.google.com/file/d/1lDZZs0PJMZVXdqdedG09hqqJqdStxwLC/view