1530s, "in a literal sense, according to the exact meaning of the word or words used," from literal + -ly (2). Since late 17c. it has been used in metaphors, hyperbole, etc., to indicate what follows must be taken in the strongest admissible sense. But this is irreconcilable with the word's etymological sense and has led to this much-lamented modern use of it.
We have come to such a pass with this emphasizer that where the truth would require us to insert with a strong expression 'not literally, of course, but in a manner of speaking', we do not hesitate to insert the very word we ought to be at pains to repudiate; ... such false coin makes honest traffic in words impossible. [Fowler, 1924]