From a marketing point of view that would be enough to slot it into the fantasy genre in my opinion. You mentioned there are religious people in your world, is the religion 'true' in your world? For example, if you think about ancient Greek myth, the gods and goddesses are involved in the story. So are the gods/goddesses of the religion in your story actually there, or are the people just following false religions and their prayers/rituals don't actually do anything?