[Aiwendil]

Is Legolas called Legolas Greenleaf or is that just a fanfic invention?

Legolas actually means "Green leaf"; it's a midst of the text translation, like saying "Eru the One".

And then in the movie Haldir calls him Legolas Thrandullian.

Really? That seems kind of strange. Adding -ion is a Quenya formula for the patronymic, but "Thranduil" is a Sindarin name.

Thorin has a last name: Oakensheild. And Elrond is called Half-Elven. And then there's Túrin Turambar. But these seem to be more of nicknames than surnames...and they're also few and far between.

Yes, these are epithets rather than true surnames. The Edain, at least during the first age, seem to have adopted some Elvish naming-practices. There is an essay in HoMe X that discusses the Eldarin naming system. Basicly, each Elf receives a name chosen by his or her father and one by his or her mother - the father-name and the mother-name. For example, Feanor was called "Curufinwe" by his father and "Feanaro" by his mother. Mother-names are often names of insight or prophecy. An Elf might also acquire names given to him by others due to some attribute or some particular deed; thus, for example, Elwe is named "Sindacollo", "Grey cloak". An Elf might also give himself or herself a name for any of various reasons. There are Elvish words given for these various types of names, but I can't recall them.

I think the Edain adopted the tendency toward epithets given by others or by oneself, though they apparently did not adopt the distinction between the father-name and mother-name. Thus, Beren is given the epithet "Camlost." Of course, the longest list of names belongs to Turin: Neithan, Mormegil, Agarwaen, Adanedhel, Thurin, Turambar, and probably others that I've forgotten.

Hobbits have an altogether different system. There is, of course, some tendency toward epithet giving, but it is of a much more pedestrian sort. Gerontius is called "The Old Took", for example. Their surnames are much more like modern surnames (they are rather more modern in general than the rest of Middle-earth); they are passed down from a father to his children. There is nonetheless something archaic about them, as if they are not yet too far removed from their epithetic origins. Thus, for example, Bilbo Baggins actually lives at Bag End, Merry Brandybuck comes from Buckland, and so forth; whereas today we have no reason to suspect that, for example, someone with the last name "Littleton" actually comes from the town of Little. It seems that the names of the lower classes in the Shire are even less well established. Sam's name "Gamgee" appears only to go back a few generations.