The word is from Latin, in which language it appeared in the third century AD as a borrowing from Greek paroemia, a proverb. In 1639 John Clarke, the headmaster of Lincoln grammar school, published an early work on proverbs, from the works of Erasmus. He gave it the title Paroemiologia anglolatina, Proverbs English and Latin. Many paroemiological collections, those relating to the study of proverbs, have been created since.
As it’s comparatively easy to find examples, it’s surprising that the recent revision of the letter P in the online Oxford English Dictionary doesn’t feature paroemiological. However, it does have a number of close relatives, such as paroemiologist, a student of or an expert in proverbs and proverb lore, and paroemiology, the study itself, as well as paroemiographer, a collector of or writer on proverbs, and paroemia itself, an adage or proverb. Apart from this last one, all were coined in the early nineteenth century.
If you prefer, as most scholarly users do these days, you can spell all these without the first o.