What is the connection between this Pasuk and the previous one?
Seforno: "Blessed is Avraham to HaSh-m... and it was by the grace of HaSh-m that Avraham defeated his enemies." Shem referred to the current Berachah that Avraham had just received from HaSh-m. 1
Maharal: Refer to 14:19:0.1:2.
Because when the Resha'im fall into the hands of the Tzadikim, there is great joy.
Who gave Ma'aser to whom?
Rashi: Avraham gave to Malki-Tzedek (Shem). 1
Riva, Chizkuni: Alternatively, Shem gave to Avraham, for HaSh-m deposed Shem from being a Kohen. 2
Gur Aryeh: We were just told that Malki-Tzedek was a Kohen (14:18); certainly it was Avraham who gave to Malki-Tzedek.
Rashi holds that Kehunah was taken away from Shem's children, but not from Shem himself. Chizkuni disagrees; Malki-Tzedek's status as Kohen was removed effective immediately, whereupon he gave his Ma'aser to Avraham.
How could Avraham give "Ma'aser of all" to Shem? We learn that Avraham did not keep any of the spoils (14:23)!
Riva #1, Moshav Zekenim (to 14:23): Really, everything belonged to Avraham, like one who saves another's stolen property from the bandits. A Chaver (one who meticulously fulfills Ma'aser) may not let matters leave his Reshus without tithing them.
Riva #2: Rashi explains that Avraham gave Ma'aser "from all his [property]," i.e. but not from the spoils. He intended only to return the spoils to the owners; he never acquired them. 1 Even a Chaver need not tithe in such a case.
Gur Aryeh: One may not take Terumah from what does not belong to him (Mishnah Terumos 1:1), and Avraham had no intention of keeping the spoils for himself. See also Radak. Ramban, however, disagrees.