What is the origin of the phrase 'Don't Dilly Dally'?

It was a common practise to reduplicate words with slight variation such as fuddy duddy, helter-skelter, tittle-tattle, willy-nilly, and dozens of others.
It appears to be a 20th century thing and dally means to waste time or dawdle

Senior Moments is correct about the etymology of 'dillly-dally'. The phrase 'DON'T dilly-dally' is generally associate with the music-hall song 'Don't Dilly Dally On The Way', sung by Marie Lloyd:

We had to move away, 'cos the rent we couldn't pay.
The moving van came round just after dark.
There was me and my old man shoving things inside the van
(Which we'd often done before, let me remark).
We packed all that could be packed in the van, and that's a fact,
And we got inside all we could get inside.
Then we packed all we could pack on the tailboard at the back,
Till there wasn't any room for me to ride.
(CHORUS): My old man said 'Follow the van
And don't dilly-dally on the way!'
Off went the van with the home pacjked in {it;}
I walked behind with my old cock-linnet.
But I dillied and dallied, dallied and dillied,
Lost my way and don't know where to roam.
I stopped on the way to have the old half-quartern,
And I can't find my way home.

Cassell Dictionary of Slang has it as 18th century in origin

True. The earliest quotation for the verb in the OED is from Richardson's 'Pamela' (1741): 'What you do, sir, do: don't stand dilly-dallying!' As a noun, 'dilly-dally' is found even earlier: there is a quotation from 1610 'Such dilly-dally is fitter for heathens that know not God'.

But I think anyone who says 'Don't dilly-dally' today is more likely to be thinking of the Marie Lloyd song than of Richardson's novel.

I agree totally with Tabby Tom that the phrase is most generally associated with the Marie Lloyd song. But in the version with which I am familiar the last two lines of the song are: O you can't trust a copper like the old time special, When you can't find your way home. Apologies for diverting from the original question somewhat.

There are three verses to the song, and the refrain differs slightly each time. The second and third verses are:

I gave a helping hand with the marble wash-hand-stand,
And, straight, we wasn't getting on too bad.
All at once the carman bloke had an accident and broke -
Well, the nicest bit of china that we had!
You'll understand, of course, I was cross about the loss,
Same as any other human woman would.
But I soon got over that, what with two-out and a chat,
'Cos it's little things like that what does you good.
(CHORUS): My old man ... don't know where to roam
Now who's going to put up the old iron bedstead
If I can't find my way home?

Oh, I'm in such a {mess;}
I don't know the new {address;}
Don't even know the blessed neighbourhood.
And I feel as if I might
Have to stay out all the night,
And that ain't a-going to do me any good.
I don't make no complaint,
But I'm coming over faint:
What I want now is a good substantial feed.
And I sort of kind of feel,
If I don't soon have a meal,
I shall have to rob the linnet of his seed.
(CHORUS): My old man ... don't know where to roam.
You can't trust the specials like the old-time coppers
When you can't find your way home.

(Source: 'The Great British Songbook', compiled by Kingsley Amis and James Cochrane.