Well, great whites and other more dangerous sharks tend to be large and rather toothy. I don't think we evolved to fear sharks, so much as fear them because they have the properties of 'things that will eat the bloody hell out of us,' the fear of which may or may not be evolved to some degree.
We actually fear sharks more than we need to. We apparently aren't terribly appetizing to them, and their attacks tend to not be fatal. Given that, we wouldn't have much of a reason to evolve a fear of them directly.