Don't forget Breelander humans, they had last names too. (And when I'm personally meddling with M-E in my RPGs, I made Haradians have last names too, just for interest...
)
I would like to point out, however, that (if I'm correct) last names as we know them is a fairly recent thing in the western world. Nobility had their family names (but there's in M-E the house of this and that to represent the same thing) but normal people, especially peasants, had no last names. If they needed more names than their own, they could use their father's name (like we could say for example Frodo son of Drogo) or their place of origin (Frodo from Hobbiton) or nicknames like
Legate mentioned above.