Correr comes from the Latin for the same, currere. Currere, in turn, comes from the Proto-Indo-European root *kurs, which also means, “to run” — just like horse does! Both have the same common ancestor.
The weird thing is: how did the PIE *kurs turn into horse, they sound so different.
The explanation is that, in the Germanic languages like English, the k- sound turned into the h- sound. But in Spanish, the original k- sound remained, although usually written with a c-.