It might be an instinct in the sense that language is an instinct. It just arises in every society even if you start a new one that is free of a common language / a religion.
That there are so many examples of mythology and other fables indicates that humans enjoy story telling. What we call _religion_ is just the mythology and fables that we stopped calling _sacred_ when the old power structure collapsed.