Personally, I don't think separating monotheism and polytheism worshippers into two separate countries that don't like each other is the best way to handle having both monotheism and and polytheism together in the same setting. There is no reason you can't have both a monotheistic religion and a polytheistic religion existing side by side in the same country.
Let's look at Hinduism, the poster child for real world polytheism, with its numerous major, minor, and local gods. However, certain sects of Hinduism are more monotheistic than polytheistic. In these sects, the highest of the gods, Brahma, the creator, Vishnu, the preserver, and Shiva, the destroyer, are seen as forming the Trimurti, a concept not unlike the Christian Trinity. Other sects of Hinduism see Vishnu as an all-powerful God, with all other deities as his subordinates. So while Hinduism is nominally a polytheistic religion, there are Hindu worshippers who can say with a striaght face that it is a monotheistic religion. (Please note that all of this is gross-oversimplifications of the extreme complexity and diversity of Hindu religion).
Another thing to consider is religious syncretism, which is very common in East Asian countries. In Japan for example, it is commonplace for someone to turn to a Shinto temple to pray for good fortune, and later ask Buddhist monks to perform a funeral. In this case, Shinto, an animist/polytheistic relgion, and Buddhism, a religion that denies the existence of gods, exist side by side, sharing the same worshippers. (Once again, any discussion of real world religion comes with the disclaimer that it is very complicated, diverse, and resistant to one-line summaries.)
I for one am tempted to use a syncretic religious model in my next campaign setting, with Divine classes associated with a monotheistic religion and Primal classes associated with an animist/polytheistic religion.