Where did the term "pardon my French" come from and why is it followed by vulgar language?

The first usages of "excuse my French" or "pardon my French" I could find come from the 19th century. You can see the Google N-grams tracking the usage of the two phrases here. Note: Google's N-gram database seems out of step with the Google Books database at present, and those earliest three examples I couldn't locate there, but some examples I can locate in the Google Books that don't show up in the N-gram database.

An early example is from a novel Two Lives: Or, To Seem and to be by Maria Jane McIntosh. In 1846 novel we see a scene like this:

The Marquis raised his glass, gazed long at the lady indicated, then lowering it, and turning to Mrs. Elliot, exclaimed [... "]The American ladies are charming, very charming, mais un pet prudes [but a little prudish]. Pardon my French: I could not be so bold to say it in English."

"I will not permit you to say it in any language, of all American ladies."

Another early example is from the Fireman's Magazine, Vol. 6, pg 177 (only available in snippet view on Google Books so you can't gauge the context, with other digitalized archives of the magazine, like Hathi Trust's, only starting from Vol. 8), where we see:

[...]very finely and are steadily increasing our numbers; we gave an entertainment in Seymour recently which was pronounced recherche (pardon my French) by all who participated.

Wishing you all health, prosperity, etc., I am

Truly yours,

D. W. C.

The meaning of recherche here isn't "search" or "research" (the two most common translations for the word) but refined, as in a "studied elegance", as my Collins French-English dictionary thankfully points out.

The churn of internet sites explaining the term, like Mental Floss or Today I Found Out include the earliest known example of the phrase, which escapes me in Google Books,

Bless me how fat you are grown . . . you will soon be as embonpoint [plump] (excuse my French) as your dear father.

(This was first published as a short story in The Lady’s Magazine and later as 1831 novel The Twelve Nights by Baron Karl von Miltie).

As similar early example, from World Wide Words website, from 1833 is:

Teddy and Lord Radstock’s son, Waldegrave, boarded the French commodore, and carried him l’épée à la main; — excuse my French.

As we can see, these early examples tend to be (but are not exclusively) rude, but are all actually French. The first example I have found where something in English was asked to be excused as "French" is (again from World Wide Words) from 1865:

Dreadful good brandy o’ yourn. Ha! ha! ha! My respects. Excuse my French.

(Dreadful used to be a strong word than it is today).

This fits with the general context of "French" in English idioms: "French leave" is leave without permission or without thanking the host (the French say filer à l'anglais), "French pox" is syphilis (a French term is apparently la maladie anglaise), "French novel" is pornography, "French kiss" is a kiss with tongue, and apparently "French letter" is old-fashioned slang for a condom (French: une capote anglaise).

It seems to have started as a meme where people would use it to insert French into their conversations. This was either to say something rude discreetly or to add a touch of class, but either way presumably it came off as quite pompous and people eventually took this expression ("meme") and turned it around to make fun of the people who would speak in such away.

While obviously the idea is quite old, it has become much more common in print since the 1960's. This is certainly related to swears themselves have become more common in print in this period. However, I would also venture that this also became a common trope in novels and especially films and is essentially self-perpetuating at this point. I would venture that it has become something used for characterization (or at least, something used as a throw-away joke) more than something actually used in daily conversations. This last point, however, is mostly conjecture as documenting oral language is much harder than documenting language's written version. I can say, however, it doesn't turn up in the corpora (sing. corpus) of spoken English I checked, like the Michigan Corpus of Academic Spoken English, though these were cursory, rather than exhaustive, checks.

"Pardon my language", I would like to note, looks very similar on Google Ngrams to "pardon my French", similar did not original start out as a cover obscenity:

Pardon my language, do not that I write with a pedantic tone, no (Science and Love, 1852)

I must, however, beg you to excuse my language and not mind the grammar or pronunciation. (Report of the International Council of Women, 1888)

I shall therefore make no attempt to excuse my language toward Gertrude Hemster. The heated conversation in which we indulged had, however, one effect upon my future course (The tempestuous petticoat, 1904)

I found an earlier version of "excuse my language" in a work by James Shirley, a dramatist contemporary with Shakespeare:

Madam, I had rather you excuse my language

For speaking truth, than virtue suffer in

My further silence ; and it is my wonder

That you, whose noble carriage hath deserved

All honour and opinion, should now

Be guilty of ill manners.

There is not actual obscenity in this scene, but rather boldness and improper implication (I think, I am not entirely sure I understand this scene as I haven't bothered to read the whole play).

I would venture that "pardon my French" also adopted its current meaning under the influence of the much older "pardon my language".

For more on English language swears, see this older post.