Fenrir is lacking.

[Culfinrandir]

Nah. It's a world of its own, that follows its own logic. This logic needs to stay coherent within itself, or otherwise the world loses it's credibility. A good fantasy world has a logical foundation that stays true to itself. When the world breaks its own logic, it's what's called a plot hole.

In that case the simple answer is that Matoya used her magic and now Fenrir can fly. She did this because your character asked her to. She can make frogs sentient and work for her so a flying Wolf is no problem.