There are many commentaries1 who understand the story differently. It's not that the King of Sedom was offering Avraham gifts, and the latter refused.
In reality, these spoils from the war were ownerless. The King of Sedom, as he was losing the battle against the other Kings, lost all hope of ever retrieving his property. As a result, according to halacha, Jewish law, they became ownerless2. When Avraham won the war and found the spoils, they became his to keep. However, the halacha states that it is the proper thing to do to act beyond the letter of the law and return the items to their original owner3. Even though Avraham would have been justified in keeping the spoils, he wanted to go beyond the letter of the law and returned them.
Rav Chaim Kanievsky asks a related question. If a person finds an ownerless object and goes beyond the letter of the law and returns it to the original owner, do they have to give ma’aser? Seemingly no, since they didn’t actually end up earning anything. He points out that the story with Avraham possibly could be a proof that yes, one should give. We see this from the fact that Avraham gave ma’aser from the spoils to Malkitzedek. Although, I would argue that perhaps just like he gave back the spoils beyond the letter of the law, he gave ma'aser beyond the letter of the law.
Either way, we see that he didn't give ma'aser from the King of Sedom's property.
1 Tur al HaTorah 14:23, Ohr HaChaim 14:21, Pardes Yosef 14:23, and Ta’amah D’Krah by Rav Chaim Kanievsky shlita ad. loc.
2 Bava Metzia 22b; Shulchan Aruch Choshen Mishpat 259:7. This begs the question why the other commentators felt that the King of Sedom was giving Avraham gifts, and Avraham was refusing them because of שונא מתנות יחיה
3 Bava Metzia 24b; Shulchan Aruch loc. cit. se’if 5
4 Ta’amah D’Krah loc. cit. He doesn't cite it, but Hafla’ah to Kesubos 50a s.v. תוס' ד"ה אל says without qualification that this is the reason Avraham gave ma’aser, as if this was a known halacha that should be followed (although he ends up saying Avraham only gave ma’aser from his own property, since it also became ownerless during the battle, and he reacquired it)