mysteries of grammatical gender. La Patrie, which means literally "the Fatherland" is feminine gender.

I think the feminineness of the word might come from its "ie" ending, not its "patr" beginning. If it had a gender in English, I'd guess the gender would probably come from the 'land' portion, not the 'father' (well, that's how it works in German, and it kinda makes sense).