Well, there is a difference between religion and just a feeling there is something supernatural on an individual level, which is all that animals without language could manage, even if intelligent. Religion implies a degree of sharing of belief, and an element of ritual. Also, most animals do not seem to have self-recognition, as far as we can tell from experimentation (a line of inquiry started by Darwin.) If you don't have proper self-recognition you don't have the ability to recognise something beyond-self.

Oh, and we have imagined far more things that have not proved to be true than that have proved to be true. The power of belief stems from the fact that we give far more attention to things that happen than things that don't, and we are inclined to imagine causation. If the grass sways, it probably isn't a lion, but you would be advised to run anyway, because if it just happens to be a lion, your life is on the line.