Genesis 14:20 says that Avraham gave "a tenth of all" to Malki-Tzedek. A tenth of what? His annual income, his assets, the booty from the war, or something else?
Rash"i there states that he gave 1/10 of all his assets ("מעשר מכל אשר לו") - which should mean his sheep, cattle, money, etc. I think the booty from the war may have been excluded, because we see a verse or two later, that he returned this to the King of Sodom. Thus, it wasn't his property. (Logically inferred, and further proof from Avraham's response to the king saying that he didn't want to be enriched by the king for even a thread.
Had he given ma'aser from the booty, based on what was "not" his (according to his thinking), he would have given it from "stolen" property. (It's an interesting question, though - perhaps, to ask a separate question on M.Y.)