What are "Amim" and "Le'umim"?
Radak: Above (57:10) I explained that both of these are families of Yisrael, like "Amim Har Yikra'u" (Devarim 33:19), and "Acharecha Vinyamin ba'Amamecha" -Shoftim 5:14). Here they refer to all nations, for they all will come to Yerushalayim at the time of the Ge'ulah - "v'Nilvu Goyim Rabim El Hashem ba'Yom ha'Hu" (Zecharyah 2:15). The Lamed in Le'umim is part of the root, like "u'Le'om mi'Le'om Ye'ematz" (Bereishis 25:23). Even though [if it is from the root] it should have a Dagesh, it does not, like "u'Michyas Basar Chai ba'S'es" (Vayikra 13:10; there is no Dagesh in the Sin) and other verses.
Malbim (67:3, Bi'urei Milos): Amim are esteemed collections [of people], with a king over them. Le'umim are Umos with a common creed.
Why does it say both "Odecha va'Amim" and "Azamercha ba'Le'umim"?
Radak (57:10): The matter is repeated in different words, like is common.
Malbim (57:10): Odeh is thanking for the good. Zemer is singing His praise; that is among Le'umim, who have a creed. I will tell them Hashem's praise, that He is greater than all Elokim.