I'm not a biology major, a vet or anything that has anything to do with anatomy. I did do some googling in consideration of this question.
First - your evolution question. If you check the mythos, Sleipnir is actually one of a kind and is a child born of a horse and Loki (Loki was the mother). Greek mythology also had its share of weird things born when gods mated with animals. My 'evolution' story for them would probably be based on Sleipnir being the forefather and the existing ones descending from him. Or maybe there were a few progenitors if Loki really liked that horse.
If you don't like that, I see the next most probable answer as your world having mammalian species with more than 4 limbs scattered across the world, either with 8 being the standard or maybe with 4, 6 or 8 depending on the ancestor. I'm no evolution scholar but I would assume land creatures generally have 4 limbs +/- a tail due to that being what we first obtained when crawling out of the sea. If your world had a few different things crawl out, you could wind up with different limb counts.
At this point, I think adding a limb to something would require extremely selective breeding over a course of hundreds, if not thousands, of generations. Adding 4 limbs...well, we'll be able to do that with gene splicing (or be extinct) faster than nature would be able to add them.
Second - How do the limbs work? I'm going to skip spider-shaped bodies, the implications of trying to set 8 legs in a circular fashion on an entity with a spine are not something I want to get into right now. If you desire a spider-horse solution, let me know and I'll ponder it. My knee-jerk answer is multiple spines.
I'd go for setting it up so that the front shoulder joints are replaced with small versions of hips - rather than a single joint, you have two side by side. The hip bones in the back would have evolved to have a similar arrangement with 4 joints coming off of them in 2 pairs. The stomach would have some sort of pouch and one set of 4 legs would generally be left in the pouch. This gives the animal the opportunity to allow the leg muscles in half the legs to be at rest at any given time, increasing stamina. The lungs and heart would expand for this, or maybe the horse actually has two sets of each to account for the extra oxygen and blood flow required to service an extra set of muscles. Spare organs is also generally an awesome feature for mythical animals.
The addition of 4 legs should add a decent amount of height + distance to the jumps, ask a physics major for specifics I'm going to go ahead and guess you'll get something like 50-80% extra.
With extra organs and legs, you're looking at a king of horses that isn't necessarily faster than another horse but will far outlast any other.