To understand how the terms chauvinism and chauvinist eventually yielded the phrases "male chauvinism" and "male chauvinist," I think it's important to look not only at the terms' original sense but at the radiating senses in which they were used during the years prior the emergence of "male chauvinism/chauvinist."
Chauvin and early notions of Chauvinism
Nicolas Chauvin may or may not have been real, but his devotion and loyalty to Napoleon and La Grande Armée are unquestionable. One of the earliest mentions of Chauvinism in an English publication appears in a translation of Albert Cler, “The Dilittante,” that appears in Pictures of the French: A Series of Literary and Graphic Delineations of French Character (1840). Cler refers to the Restoration (of the Bonapartes) in France as a time “when Chauvinism had monopolized every thing, not even excepting crockery and pocket-handkerchiefs,” and then either Cler or his English editor adds this footnote:
Chauvin was the pseudo-author of a popular song, consecrated to the glory of the French army.
Benjamin Vincent, Haydn's Dictionary of Dates (1874) offers this alternative note:
CHAUVINISM, a term derived from Chauvin, the principle character in [Eugène] Scribe’s “Soldat Laboureur,” a veteran soldier of the first empire, filled with intense admiration for Napoleon and for all that belonged to him.
The play Le soldat laboureur (from the 1830s) is elsewhere described as lampooning Chauvin; Scribe may not have been the play's author, however.
A Google Books search finds an upsurge in occurrences of Chauvinism starting in the 1860s. One precise account of what the term meant (in English) at that time appears in “The [Franco-Prussian] War)” in Fraser’s Magazine (November 1870):
The political principle to be fortified in this manner was ‘Chauvinism,’ which consists mainly of three elements: contempt of all other nations as inferiors in civilisation and military genius; an arrogant desire to dictate to them not merely in international matters, but even in their domestic affairs; and a fixed determination to tear the treaties of 1815 to shreds, especially those parts relating to the Rhine frontier and Belgium.
Another interesting discussion, from 1901, compares Chauvinism to Jingoism as characteristics of a certain type of French citizen and a certain type of Briton. From Joseph Fitzgerald, Word and Phrase: True and False Use in English (1901):
Jingo and Chauvinist (chauviniste), Jingoism and Chauvinism (chauvinisme), are two pairs of synonyms, Jingo and Jingoism denoting the madly patriotic Briton in his defiance of a world in arms; and Chauvinist and Chauvinism designating the like exaltation of patriotic sentiment in the perfervid Gaul. …
Chauvinist is formed from the name of Nicolas Chauvin, a gallant private soldier in the armies of the first French empire. His devotion to Napoleon knew no bounds; whatever Napoleon did or said was for Chauvin best, wisest, and most beneficent. In a vaudeville, the “Cocarde Tricolor” (“tricolor cockade”) , was introduced a character named Chauvin, whose principal act was to render a song chockfull of patriotic sentiments and glorification of French valor.
In its unadorned form, then, chauvinism in the nineteenth century describes extreme nationalism, often in the specific context of France; and a chauvinist is an adherent or practitioner of chauvinism.
Varieties of chauvinistic experience
Long before dictionaries broadened their definitions of chauvinism to account for senses of the word that didn't have much to do with nationalism and patriotism, however, the word appears in situations where a prefacing adjectives sharply narrows its focus. Most, but not all of them still focused on national patriotism in various forms.
For the period between 1872 and 1936, a Google Books search finds matches for such concepts—quite apart from the nation-specific forms one would expect to see (French, English, American, German, Russian, and the like)—as egotistical chauvinism (July 1872) intellectual chauvinism (1879), religious chauvinism (July 1879), scientific chauvinism (1885), artistic chauvinism (May 1887), philosophical chauvinism (1887), musical chauvinism (June 1888), literary chauvinism (1890), racial chauvinism (December 1900), collegiate chauvinism (1902), linguistic chauvinism (May 1903), medical chauvinism (1903), international chauvinism (1906), primitive chauvinism (1911), East [Coast] chauvinism (November 1912), cultural chauvinism (October 1914), pacifist chauvinism (1917), moral chauvinism (1917), spiritual chauvinism (April 1917), æsthetic chauvinism (1922), proletariat chauvinism (1922), black chauvinism (1924), white chauvinism (1930), financial chauvinism (1931), alien chauvinism (1936), and even communo-chauvinism (1936).
Most of these chauvinisms appear at bottom to refer to something like “venomous hyper-patriotism” as applied to a particular country and to the disadvantage of all other countries, whose productions in that area are despised by the chauvinist. But others, like “East Coast chauvinism,” refer to regional parochialism; still others, like “racial chauvinism,” describe non-national extremism, and some, like “moral chauvinism,” are difficult to make any sense of.
One early dissent from the notion that chauvinism necessarily entailed preoccupation with supposed national superiority is this comment from a review of A. Stopford Brooke, Primer of English Literature, published in The Dublin Review (October 1878):
But there is another kind of Chauvinism, which is an affair of race, not of nation, which is not English, but Teutonic, and the growth of which is not in any way to be desired. This is the Chauvinism which makes Mr. Brooke say (p. 8), “ Otherwise, we English have nothing to do with the old dwellers in our country.”
This view was implicitly taken up in the Communist Party USA’s decades-long campaign against what it called, by 1930, “white chauvinism” in its own ranks.
By then, the words chauvinism and chauvinist had come to be used—especially in leftist terminology—in a much broader sense—something like “irrational, reactionary extremism” and “irrational, reactionary extremist”—which, not being pinned specifically to nationalism, allowed people to associate the terms with political, cultural, and social subjects of all types.
Chauvinism in leftist discourse
According to Carl Ratner, Macro Cultural Psychology (2013), which is cited in Marius Hancu’s very useful answer,
Male chauvinism was coined in the United States by women members of the Communist Party in 1934 [citation omitted]. It was part of the party’s attempt to understand sexist and racist behavior and attitudes as fostered by the exploitation of the capitalist system.
As such, it was a companion notion (though later by four or five years) to the CPUSA’s idea of “white chauvinism”) discussed earlier.
As Josh61's question anticipates, the first instance of “male chauvinism” that a Google Books search finds is from Clifford Odets, Till the Day I Die (1935):
TILLY: Dammit, I’ll do your work.
TILLY: Why not ?
ERNST: Tempting, but improbable.
TILLY: You and your male chauvinism!
ERNST (with smiling protest) : No, Tilly, no.
TILLY: To-day I'm particularly concerned with you.
The Wikipedia article about Odets reports that he was a member of the Communist Party “for less than a year, between 1934 and 1935,” so he would have been well aware of the contemporaneous slogans and catch-phrases of the CPUSA.
In its traditional sense of “nationalist,” chauvinist seems to have been a favorite polemical word of Lenin, as for example in the (translated) 1918 edition of his “International Socialism,” published in N. Lenin & Leon Trotzky, The Proletarian Revolution in Russia (1918):
We Russians do not as yet realize that the majority of the Zimmerwald International was dominated by [Karl] Kautsky. But this is an absolute fact which can not be minimized and of which Western Europe is fully aware. A chauvinist, an extreme German chauvinist, Heilman, editor of the arch-chauvinist Chemnitz Gazette and contributor of the arch-chauvinist Bell (a Social Democrat, of course, and an ardent partisan of the Social Democratic unity) was compelled to acknowledge in writing that the “center” (or Kautskians) and the Zimmerwald majority were one and the same thing.
In the course of that book Lenin also introduces the concept of “social-chauvinism,” which he thoughtfully defines for the unschooled reader’s benefit:
It is obvious that in its essential traits, politically and intellectually, chauvinism is identical with opportunism. Opportunism placed in the special environment of the present war [the Great War] becomes social-chauvinism. The main idea of opportunism is that of the co-operation of all classes.
So according to Lenin, social-chauvinism is something like forgoing class interests in the name of national (and hyper-nationalist) solidarity. Lenin had elsewhere (in 1914) identified a thread of chauvinism that he referred to (in translation) as “Tsarist—monarchial—chauvinism.”
Because Marxism saw itself as essentially internationalist in scope, focusing on the interests of the proletariat, its exponents tended to view chauvinism as deeply unscientific and regressive, which made it a popular dismissive epithet in a multitude of contexts—race, culture, political ideology, and (eventually) gender. At one point in the 1930s, the Communist Party even floated the notion of “anarchic chauvinism”—presumably a befuddled mindset of extreme nationalist anti-statism—that a member of the Mexican renaissance of the 1920s and 1930s accused himself and his fellow artists (most notably, Diego Rivera) of in May 1934 in New Masses.
Male chauvinism’s second wind
The terms “male chauvinist” and “male chauvinism” never went away after debuting in 1935 (in fact, J. Edgar Hoover mentions "male chauvinism" in his book Masters of Deceit ); but they didn’t emerge from the welter of other specialty chauvinisms until the late 1960s, as this Ngram chart suggests:
The adoption of those terms by advocates of feminism in the late 1960s clearly accounts for this development. However, it isn't easy to isolate the particular instance that triggered its general adoption. Kate Millett uses "male chauvinism" (and "female chauvinism") in her highly influential book Sexual Politics (1970); but before that, Ti-Grace Atkinson uses the term in a December 12, 1969 Life magazine article; Beverly Jones and Judith Brown use it in their pamphlet "Toward a Female Liberation Movement" (1968); and unidentified authors use it multiple times in a 1967 magazine called The Activist. Earlier still is this excerpt from Princeton's University newsletter (1966):
Did one detect perhaps a trace of male chauvinism in that phrase "nice young ladies?" And was male chauvinism one possible result of educating men separately from women?
"Well, I don't think so," smiling. "A lot of Princeton graduates marry girls from Vassar or Smith — colleges like that — and if they do have any male chauvinism they get it hammered out of them pretty quickly!"
One can imagine that the complaint "You just don't get it, do you?" arose out of colloquies like this one.