Just something I was wondering. If all phones were landlines, that would seem redundant.
This is not an answer.
Google ngrams shows at least a use of the word since the 1940s. Remember that telegraphs and radio existed when telephone land lines came to be. If you are more interested in the history of the creation of the word and usage you might have a good shot over at /r/asklinguists.
The Oxford English Dictionary notes that "landline" was originally used to refer to telegraph wires than ran over land, but by 1965 came to also refer to phone lines.