Well, it is a bit complicated and most native Czech speaker don't know the origin. I had to look into a dictionary. Nenávidět(i) is derived from Old Czech náviděti. However, the dictionary lists two meanings of this word, one is to like or love and the other is the exact opposite (to hate)!
The old náviděti is indeed supposed to be an imperfective verb akin to viděti, that was a very good guess! I didn't know that.