I don't believe this comes from the Marquis of Waterford, when all the early citations point to a US origin. I thought it would be interesting to trace the US origins to confirm or refute this. From what I found, this phrase came from 1880s Kentucky, USA, and described cowboys riding into town, getting drunk and causing havoc.
Marquis of Waterford
Here's a contemporary account of the Marquis painting people and doors and windows in 1837 Melton Mowbray, UK, but there's nothing (verifiable) in Google Books for paint the town red from before 1884, then suddenly eight examples, I think all American, and most inside quotes suggesting it's a new phrase.
Oxford English Dictionary
The earliest OED citations are from the US. The first from a July 1883 New York Times:
Mr. James Hennessy offered a resolution that the entire body proceed forthwith to Newark and get drunk.? Then the Democrats charged upon the street cars, and being wafted into Newark proceeded, to use their own metaphor, to ‘paint the town red’.
The second is an 1884 US Boston Journal:
Whenever there was any excitement or anybody got particularly loud, they always said somebody was ‘painting the town red’.
US newspapers: a Kentucky origin
Searching the Chronicling America newspaper archive, I found many examples from 1882 and 1883, before the OED's earliest July 1883. Most interestingly, all are from Kentucky papers. In 1883 and subsequent years, the term quickly spread to other states.
Semi-Weekly Interior Journal (Stanford, KY) of March 10, 1882 says:
The Frankfort correspondent of the Louisville Commercial writes of the lobby at Frankfort: [...] He gets on a high old drunk with a doubtful old man, and they paint the town red together.
The Bourbon News (Millersburg, KY) of April 11, 1882 says:
Nicholasville has an organization known as the "Dirty Dozen," who has been daubing the town with red paint, in very unchristianable names.
The Hartford Herald (Hartford, KY), September 13, 1882 describes the prelude to a drunken fight:
Last Saturday evening some of the boys from the country came to town and got on a regular high daddy and proceeded to paint the town red.
Again, the Semi-Weekly Interior Journal (Stanford, KY), this time of November 10, 1882:
The boys wanted to paint the town red and jollify generally Wednesday night, but on account of the illness of Mrs. J. J. Williams, the fun was postponed.
The Breckenridge News (Cloverport, KY), December 13, 1882 describes a "Shooting Affair at Leitchfield":
A young man of Grayson county named John Jay Hayrraft, who has so conducted himself of late as to render him any thing but a valuable citizen, rode into Leitchfield the other day, got drunk, and, as was his general custom, began to paint the town red.
Again The Hartford Herald (Hartford, KY), this time of March 28, 1883 says:
Several of Owensboro's young bloods painted the town red Saturday night.
The Daily Evening Bulletin (Maysville, KY), June 22, 1883 has a story about "The Bad Boy":
"Well, I think the finest thing is that story about the prodigal son, where the boy took all the money he could scrape up and went out west to paint the towns red. Ge spent his money in rioutous living, and saw everything that was going on, and got full of benzine, and struck all the gangs of toughs, both male and female, and his stomach went back on him and he had malaria, and finally he got to be a cow-boy, herding hogs, and had to eat husks that the hogs didn't want, and got pretty low down.
This particular story was re-printed in newspapers around the country.
Dictionaries: The Wild West
Early dictionaries say this was a cowboy phrase.
The 1888 entry on Americanisms in the British Chambers's Encyclopaedia says (bottom left of page 228):
New slang arises rapidly, and is widely diffused with extraordinary speed. At one time the cant phrases of the western miners overran the country like wildfire ; at present, the dialect of the cowboys who ' paint the town red, ' reverberates from state to state of the Union.
John S. Farmer's 1889 dictionary of Americanisms, Old and New also includes three 1888 citations:
TO PAINT THE TOWN RED. - To go on a drunken spree, and
generally " to act the fool."
' He stains the town incarnadine,'
The Boston maiden said.
The western maid remarked, ' You mean
HE PAINTS THE WHOLE TOWN RED."
- Washington Critic, 1888.
The flannel shirt is an excellent thing
To wear on a summer day,
And we don't object to the style at all-
But what we were going to say
Is,
That
A man who will wear a flannel shirt,
And hold up his pants with a sash
As RED as a TOWN that is PAINTED right,
Is the man that we want to smash.
-Washington Critic, 1888.
But as Lumpkin takes in the money he
spends it like a Prince. After a big day's
business he has been known to blow in
one thousand dollars in a single night
PAINTING THE TOWN RED. The result is
that when the office is open for business
the next morning the cash drawer is empty.
-New York World, 1888.
John S. Farmer & W.E. Henley's dictionary Slang And Its Analogues Past And Present
1903 says:
To PAINT (or VARNISH) THE
TOWN RED (or CRIMSON), verb.
bhr. (American). See quot.
1889. Detroit Free Press, 9 Mar.
PAINTING THE TOWN RED undoubtedly
originated among the cowboys of western
Texas, who, upon visits to frontier towns,
would first become very drunk, or pretend
to be so, and then mount their bronchos,
gallop up and down the principal street,
shooting at anything, and signifying their
intention to PAINT THE WHOLE TOWN RED
if any opposition to their origies was
attempted. It was a mere extravagant
threat : one constable could usually put
the whole band in the calaboose.
1891. Harry Fludyer at Cambridge,
105. Now, do come ... to see us row.
We've got a good chance of going head,
and if we do, my eye, won't we PAINT THE
WHOLE PLACE RED on Tuesday night !
1892. Pall Mall Gaz., 17 Oct., 2, 3.
He appears here as the typical Johnnie
. . . whose aid is sought by young men
who are desirous of PAINTING THE TOWN
RED.
The Queen's Highway From Ocean to Ocean (1887) by Stuart Cumberland describes his trip across Canada.
To 'paint a town red' is, I ought to explain,
a Western expression, and signifies the height of
reckless debauch ; and when a cowboy, having drunk
his fill of whisky, has set daylight with revolver
shots through the hats of those who have ventured
to differ from him, and has smashed all the glasses in
the drinking saloon with his stock-whip, and galloped
with a wild whoop down the principal street to the
danger and consternation of the inhabitants, he may
fairly be said to have done his part towards painting
the town red.
Newspapers: Fireworks and bonfires
But why paint the town red? Whether the source of the phrase or not, it was used soon after to describe fireworks and bonfires lighting up the sky, especially during the 1884 US presidential election.
A November 7, 1884 edition of The Lawrence Journal of describes partying in Wichita, Kansas:
The excitement in this city for the past forty-eight hours has been intense; nothing like it was ever witnessed before, at least not in this city. The whole male population all day yesterday and again last night until past midnight filled the street in front of the Eagle office, singing, shouting and hurrahing, only ceasing a moment to hear dispatches read. To-night again the democrats attempted to paint town red with bonfires, music and fireworks. The demonstration had hardly concluded, when the republicans took it up, and now the noise is simply confusing.
A June 7, 1884 New York Times mentions Chicago bonfires and drinking and parting in the same article as the phrase:
The streets are alive with crowds and bands of music and bonfires light up many of the broad avenues. ... A merry party of Massachusetts delegates dined at one of the tables in the Leland House, and drank the health of the head of the ticket in bumpers of champagne. ...
It is not to be expected that they will join in painting the town red to-night, for the packing of their wagon trains is readiness to return to the East is of far more important to them.
Finally, an October 13, 1885 New York Times report on elections in Columbus, Ohio:
The enthusiasm is beyond anything witnessed here for years. The Republicans are painting the town red. Bands are parading the streets, bonfires burning, and fireworks exploding.
These are clearly mainstream uses after the term has spread "like wildfire" from "the dialect of the cowboys". Bonfires, fireworks and cannon was fired in celebration, in addition to marching bands, singing, partying and drinking, and it seems likely journalists applied the already known phrase to a situation where both the sky was both painted red by fire and there was much drunken merriment. Some newspaper uses are just about boozing.
Drunk cowboys might not light bonfires or fireworks to light up the sky, but perhaps they instead fired their guns into the air.