"Fickle mistress" is not a compound word as it is, it is a usage came in to being probably in 1745 (The Agreeable Companion; Or, The Universal Medley, &c, Volume 1) as the Google Books Ngram Viewer shows.
The etymology of 'fickle' and 'mistress' separately can be seen as follows:
From Online Etymology Dictionary
c. 1200, "false, treacherous, deceptive, deceitful, crafty" (obsolete), probably from Old English ficol "deceitful, cunning,
tricky," related to befician "deceive," and to facen "deceit,
treachery; blemish, fault." Common Germanic (compare Old Saxon fekan
"deceit," Old High German feihhan "deceit, fraud, treachery"), from
PIE *peig- (2) "evil-minded, treacherous, hostile" .
Sense of "changeable, inconstant, unstable" is from c. 1300 (especially of Fortune and women). Related: Fickleness. Fickly (c.
1300) is rare or obsolete. Also with a verb form in Middle English,
fikelen "to deceive, flatter," later "to puzzle, perplex," which
survived long enough in Northern dialects to get into Scott's novels.
Fikel-tonge (late 14c.) was an allegorical or character name for "one
who speaks falsehoods.
early 14c., "female teacher, governess," from Old French maistresse "mistress (lover); housekeeper; governess, female teacher"
(Modern French maîtresse), fem. of maistre "master" (see master (n.)).
Sense of "a woman who employs others or has authority over servants"
is from early 15c. Sense of "kept woman of a married man" is from