What makes fantasy, fantasy? Is it magic? Is it the low-tech level? The inclusion of creatures from mythological and folkloric sources? What makes a fantasy novel not a science fiction or horror novel?
Interesting question. Science fiction must be based in reality. You can extrapolate and exagerate, but you must start with the basics of how the universe operates and go from there. Fantasy can break all the rules--anything goes. Magic is often a critical piece of fantasy, but it does not have to be. I think you can use mythological creatures in Sci Fi. My own Sci Fi stories include dragons and werewolves, beings that evolved in our universe within known rules of chemistry and physics. It is sometimes difficult to categorize stories. Piers Anthony's old dual-world "Split Infinity" series does a great job juxtaposing Sci Fi and fantasy. I say who cares if you have great characters and a great story. That's why we use the term speculative fiction now. It is too hard to pigeon-hole many works.
I think that it's the tropes that make up a genre, the things you'd expect to see when you open up a fantasy novel. They can be twisted, subverted or satirized, but they're the conventions of the genres, you know?