After Melava Malka, does one recite “Al Naharos Bavel” or “Shir Hama’alos” in Bentching?
Our custom is to recite Shir Hamaalos and Livnei Korach any day/time upon which Tachanun is not said.
Therefore, on a regular Motsaei Shabbos these should be recited only if the Birkas Hamazon is being said before Chatzos, as Tachanun is not recited up until that time.
היום יום י׳ אד״ר. שולחן מנחם ח״א ע׳ 377.