How (and why) did the phrase "excuse my French" come into use to mean what it means?

It was the opposite. In the nineteenth century (and to some extent even today) French phrases were seen as fashionable and classy. The first recorded uses of "pardon my French" were quite literal.

Here's an example:

"The American ladies are charming, very charming, mais un peu prudes. Pardon my French: I could not be so bold to say it in English."

Maria J. McIntosh, Two Lives, or To Seem and To Be, New York: Appleton, 1847, p. 103.

At some point, the phrase began to be used non-literally. It's not clear when exactly that happened, but the non-literal use seems unknown to the first edition of the Oxford English Dictionary (relevant volume published 1901). The first example I've found of the non-literal use in Google Books is this from 1919:

Well, the first thing is that they are the next war, the big war after this one's over. The job is to keep it down till peace comes. Then hell will pop—if you'll pardon my French. I'm all for labor getting its rights, but some of the men don't want the right to work—they want the right to loaf.

Rupert Hughes, The Cup of Fury, New York: Burt, 1919. p. 110

There was a silent movie titled Pardon My French produced in 1921. The New York Times review is amusing:

Goldwyn star Vivian Martin is the lead in this farce, which has a plot that was overdone even in 1922 [sic]. Irvin S. Cobb brightens things up a bit with witty title cards. Polly (Martin) is a pretty young actress who is down on her luck. To make money, she poses as a French maid and is sent to work for Hawker (Thomas Meegan) and his family, uncouth Midwesterners who have struck oil and become wealthy. One of Polly's jobs is to teach the family manners, a task which is pretty much impossible. On top of that, the Hawker's son, Zeke (Ralph Yearsly), tries to romance her, while she much prefers Mac, a famous actor who is a neighbor (Wallace Ray). Countess Carstairs (Grace Studiford) and the Marquis de Void (Walter McEwen) -- fake nobility but real swindlers -- worm their way into the Hawkers' lives in order to steal their money. The Hawkers eventually come to the realization that they belong back in the Midwest, while Polly accepts Mac's marriage proposal.

/r/AskHistorians Thread