The origin appears to be unknown. The word forms include lallygagged and lallygagging.
The OED gives examples of early usage, and this one caught my eye:
“The lascivious lolly-gagging lumps of licentiousness who disgrace the common decencies of life by their love-sick fawnings at our public dances.” Northern Vindicator (Estherville, Iowa), 1868.
That’s impressive alliteration and I only wish I could view the rest of the newspaper article (or letter – I bet it’s from a letter).