This is actually not too hard to do, or at least this part isn't. The hard part is having two sentient races evolve at all, but even that I don't think is as hard as people think. All you need is for your Humans and Elves to have a (close) shared humanoid ancestor, to effectively be the same species the same way a poodle and a wolf are and the genetics works perfectly fine.
The short answer is to have the a starting humanoid species that is cut off from other humanoids for a decent length of time (but not too long) allowing them to grow and develop on their own. Each of these humanoids would adapt differently to their enviroment, growing different traits that made them different races. You simply need to make sure that they were isolated for awhile before the meet up again (at which point koinophilia would ensure they stayed separate races).
Easiest would be to go with the idea of migration of your primitive humanoid over land bridges that later got swallowed by the ocean, just as African people expanded to the Americas & Australia etc. Except make sure that they spent a bit longer on these separate land masses, long enough to develop into more distinct species rather then just humans with slightly different skin color or facial features as on Earth.
Once they met up they would be almost exactly as you described in how their mating would work. The only hard part here is keeping them separate long enough to become distinct 'races'. The original primitive 'humanoid' they all evolved from would likely have to be sapient, or at the very crusp of it, for these species to all be sapient. However, once sapience is reached technology starts evolving and very quickly (from an evolutionary stand point) they get boats and other means of traveling and meeting up with other races, which limits the length of time you have for the species to adapt. If you cared to get that deep in thought I would either make up an excuse why they early humanoids were slower to develop technology or create some strong environmental influences that would push the humanoids to evolve in differently quickly.
Now, to get into the more detailed sciency discussion of how the evolution would work, and why this is 'easy'. But first lets assign a naming convention, I'm going to use 'race' to refer to creatures that can mate to produce viable fertile offspring, even if habitat or mating behaviors would prevent it normally, but are clearly vastly different in phenotype, such as dog breeds or your elf vs human, so by race I'm implying a bit more then just a different skin color as it means on Earth.
Mutts vs Mules
As you said you don't expect genetically different species to interbreed, no dog/horse hybrids. However, genetically similar species can often produce offspring, rather or not that offspring is fertile. There are lots of factors that affect rather two creatures can produce offspring at all, I won't get into any other then chromosome number for now, but as a general rule of thumb closer genetics mean more viable offspring. This in turn means the closer evolutionary they are, ie the shorter the length of time between when the species had a shared evolutionary ancestor, the more likely the are to be viable. Of course the closer they are evolutionary the more similar they usually appear, which is why it's usually easy to identify creatures that might be able to interbreed just by looking at them and seeing how similar they look.
However, let's focus on the concept of fertile offspring, since I assume you want your hybrids to be able to produce hybrids of their own.
To go with your first two examples of mutts and mules, why are they different? Why can dogs, or in fact most canines, interbreed to produce fertile offspring, but not horse and donkey?
Genetically equines are similar, having a shared ancestor not too far back evolutionary, and can safely (mostly) produce offspring with each other easily, the offspring is just usually infertile. They are genetically viable, the problem is chromosomes. These equines offspring usually have an odd number of chromosomes, resulting in fertility issues. This is because equines all have a different number of chromosomes, 64 for horses, 62 for donkeys, and 32-46 for zebras. Thus while genetically very similar, and able to produce offspring (zedonks, zorses, mule, Hinny etc) their offspring will usually be infertile due to having the 'wrong' number of chromosomes (little over simplified here but good enough). Equines last genetic relative was 4 to 4.5 million years ago, far less then the time between human and apes.
Dogs, and in fact most major canines, all have exactly 78 chromosomes. Thus they can all interbreed with each other because their offspring will always end up with 78 chromosomes as well. In short, so long as everyone keeps the same chromosome number they can be different 'races'. Of course canines last genetic ancestor was around 40,000 years ago, a blink of an eye in evolutionary time, which is part of why they have not had time to diverge more.
Human species, races, and humanzee
Now to your last example, why can't humans interbreed with apes? Our last genetic ancestor with chimps (including bonobo) was six to seven million years ago. However, that doesn't mean we aren't compatible, genetically were very similar. Look at bonobo and chimpanzee, our two closest genetic relatives. They are able to produce fertile offspring, quite easily, though they 'only' have been separate for 2 million years. In fact, if you look at our genetic difference compared chimp/bonobo we are about as different as equines are! That's right equines, who can produce offspring (some pairings a bit harder then others, but all can). So shouldn't we be able to produce offspring with apes?
A large part of the problem is again with chromosomes, and humans causing trouble. Some time in our history, after splitting off from apes, two of our chromosomes fused together into one chromosome. This means we have exactly one less chromosome then apes, and different number of chromosomes make mating much harder. This is a large part of why we are incompatible with apes.
However, Equines also have a different number of chromosomes and produce hybrids semi-easily. So then why aren't we still at least semi-interfertile? Who knows, we can't point to a specific reason that makes us entirely infertile with apes. It basically comes down to how our chromosomes have changed. Presumably some random mutations happen to be less compatible with apes than would be expected.
Actually, we can't say with 100% certainty we aren't capable of producing hybrids with apes, in theory. We're almost certainly not usually inter-fertile, but many species generally thought to be less fertile have had random successful mating. Certain studies rule out fertility with non-apes but in theory we can't say for certain that a rare hybrid with chimp/bonobo isn't possible. After all, mating between human and bonobo don't happen very often, so if there was a 1/1000 chance of a hybrid it would take quite a while for that to actually lead to a hybrid being produced, and we may not catch it when it happens. However, I'd say the odds are pretty slim :)
However, my point is that our lack of fertility with apes is almost as much a fluke as a rule. If our chromosomes hadn't decided to fuse we may be making monkey hybrids left and right. Generally speaking we are more divergent evolutionary from apes then equines and canines are from each other, which no doubt plays a role, but it comes down partially to chance and how mutations played out. Different humans on a parallel earth may very well have been fertile with Apes if a few mutations happened differently.
Proto-human love
Of course that doesn't mean we weren't fertile with any apes. Before Homo Sapiens showed up many other homo-whatevers existed, proto humans, and many of them interbred. Most interesting, humans interbred with our close genetic relatives, the neanderthal!
That's right, in our not-that-distant-past we had two races of humanoids, homo sapiens and neanderthal, with very real physical differences. Both species were intelligent, arguably sapient, used tools etc etc, their differences were just the same as elf and human; or perhaps elf and troll (neanderthal were larger, stronger, and better equipped for running, but needed more food due to this, which may have been part of how we ended up outcompeting them). These two races produced hybrids, and those hybrids stayed and mated with their parent species, we know this because we have found neanderthal DNA in modern humans.
Thus we already have your perfect example having happened in our own history. Sure the Neanderthal died out, but nothing said they had to. If they had adapted a little better to the pressures that killed them they may have lived on to develop into a more 'modern' race. Of course it's possible our interbreeding is what 'killed' them, that eventually they became part of humans rather then being a separate race, who knows.
The point is that races that can interbreed the way you want are common, it is random fluke that humans are not compatible with other species. Your multi-race world existed in the past, but humans ended up being the only ones that made it to the modern era. If other sapience humanoids managed to survive to modern era we would be able to produce cross-breeds just like you suggested.
So how do we make them survive?
So the real question is simply how to ensure multiple sapient species survive. My suggestion is to isolate them from each other, as I already said having them migrate to different continents and then be cut off from their home continent is the easiest option. If you want 'underground' races (dwarf, gnomes, etc), that's easily done by making them simply have found a niche living underground and evolved for it as well.
The thing you need though is to keep them separated for awhile, so they have time to change without interbreeding. This is how any species comes about, the two species need to be isolated for mutations in each group to not spread to the other group long enough for those mutations to make them distinct entities. Particularly in the case of sapient species this isolation likely becomes a bit more important to think about, since we would find ways around many things that isolate other species (Bonobo and chimp are genetically viable and live practically on top of each other, the nile separates them. A simple technology in their past and there would be no difference between the two because they would have interbred).
You also need the separation length of time to be long enough, thus why I tried to show the length of time between the common ancestor of each species. the canines are 40,000 years apart and interbreed easily, but are also so similar it hardly seem far enough apart to be a different race (I'm talking wolf vs coyote etc, dogs are vastly different due to human breeding and thus shouldn't be looked at for an example of 'natural' evolution). So I would look at making sure you kept your humanoids separate for at least 40,000 years.
Equines with 3 million years apart are a bit too genetically different, so you probably don't want your species separated that long, but that isn't an issue,. Your problem is keeping a nearly-sapient species from developing boat technology in 40,000 years. Once sapience is achieved technology will develop rapidly.
I would suggest further picking the features of your different races you want to be distinct and come up with a justification why they were evolutionary advantages. The more significant an advantage these are the easier it is to justify their evolution rapidly.
However, I think this is pretty easy to handle, and is also more a world-building question about how to allow multiple sapience to evolve at this point. The key part is that they will interbreed once they evolve without any real work, it's how their genetics will exist.
Genetic curiosities of your hybrids
Blanket term, but having gone over how they could evolve lets talk about some interesting details that factor in to such species.
Not all must be fertile
As I said humans were kind of odd in that we really didn't need to be as infertile with apes as we ended up being, it is unusual that we are less fertile with chimps then one would expect. However, it's not impossible for this to happen with other species. You could have some humanoids that are not fertile with others. Or, like equines, you could say some humanoids have a harder time producing offspring together but can. Perhaps human-orc hybrids are common, but elf-gnome hybrids are very rare. You have some wiggle room to affect how easy hybrids are produced for a given combination of races, though as a general rule of thumb most races will be mostly inter-fertile and only a few combinations will struggle with producing offspring most likely, owing to how close their most recent common ancestor likely was, due to the whole sapience means technology comes fast argument from earlier.
Going along with this it's also possible to say some hybrids are not fertile while others are, or then some hybrids usually aren't fertile, but with varying chance of fertility. The more time you put between humanoid's last common ancestor the more you can get away with these sort of incompatible hybrids, most will be compatible without issue.
Due to Haldane's rule if you decide to have some hybrids that are not always fertile it's the males that will usually be infertile, while females may still be fertile.
Likewise when hybrids that are rare a hybrid will be far more common if the father is from the species with fewer number of chromosomes. I don't expect you to know how many chromosomes your races have, but the point is that if a hybrid is rare one cross (race x father with race y mother) may be more common then the other (race y father with race x mother).
I'm so depressed to be a cross-breed
There is a concept called Outbreeding depression, which basically says that if two organisms are very different then a child produced by them is likely to be less viable then a child produced by two parents that are more similar. This principle is not limited only to hybrids, but is most evident with them. Not all species will suffer outbreeding depression, some may even experience the opposite phenomena of inbreeding depression, but generally outbreeding depression is more common.
Outbreeding depression can be caused by many reasons, but there are two big ones.
Races evolve to fit niches, but if a hybrid is halfway between two races he is half way between two niches, not fitting in to either. This often hurts him because he can't survive in either niche. Imagine a half human, half dwarf. He may lack the vision to see in the dark of a mountain and instinctual be claustrophobic, making him unable to live with dwarfs. However, his small stature, without the equivalent dwarven strength, may make it hard to live in a human village where everything is built for someone taller, thus he struggles in both areas.
Genes don't match up perfectly. Race X may use a gene to regulate some trait and race y a different gene, a hybrid of the two may fails to get either gene, causing something to be out of kilter. For example, in dogs you never ever mate a large male to a tiny female. They will happily mate (dogs have been bred to be very...sexually liberal?), and the male often will find a way to do the deed even if he seems too big. However, the pups will have genetics deciding their size based off of both parents, meaning they will grow to be roughly half way between size of mother and father. The problem is that the mother, and her womb, are still much smaller then that size. This means that the pups will effectively grow too large to fit within her womb, dying when they run out or room to grow and quite possible killing the mother in the process. The combination of genes clearly had very unfortunate side effects even if they could breed.
You should keep this in mind, the hybrids will likely struggle compared to 'pure-bread' species. In particular I would remember example 2, that some oddities may show up when mated together.
However, outbreeding depression can occur rarely at times too. Some traits may be better off for hybrids then the pure-breeds, this is just less common the the opposite. For instance zebra-horse hybrids were bred because they were more tolerant to diseases than either parent species in certain areas of the world. And mules are bred because they are strong while still being more even-tempered than donkeys.
Generally speaking when outbreeding helps it will be in one or two unique areas, not necessarily everywhere. The Zorse for instance was more immune to disease, but was generally less useful as a pack animal than a horse otherwise. Just because your hybrid gets one or two odd positive traits, (better eye-sight, stronger ability to sense magic, grow to adulthood faster etc), doesn't mean that all of him will be better. In fact you're likely to get a bit of both at times, with a hybrid suffering by not fitting into either parent species niche, but perhaps getting one or two things he is better suited at as well.
Sometimes you get a more complicated example. Like the Liger (half lion, half tiger). The Liger is HUGE, much bigger than either species, due to a fluke of genetics. This could make him much better in a fight potentially, but comes at the down side of needing much more food to eat, and being slower, more prone to health issues since his body can't support its own size, and likely worse at actually catching prey etc. All things considered the large size is likely a weakness in many ways, but it does have some benefits as well.
Of course the easier it is for a race to interbreed the closer their genetics are, which will mean an example like the Liger is less likely to occur, these sort of extreme difference are more common the more different the parent species are.
Darwin's Dilemma - why aren't we all hybrids?
Think about it, if two races are living close together you would expect a lot of matings between them, and their children will mate, etc etc. After a while you get a whole bunch of hybrids of various degree, to the point where a 'pure' race individual is hard to find...wouldn't you?
This is actually a real question Darwin himself had: why do species exist at all instead of a random collection of hybrids all along the species hybridization line? The answer is koinophilia.
In short, we will instinctually not find other races (again, I'm talking fantasy races, not races on Earth) as attractive. As I said, most hybrids will suffer from outbreeding depression, meaning most of the time if you mate with another race you get a child that will be weaker, struggle, and may not be able to find a mate of its own. Thus over millions of years of evolution we, and all animals, evolved an instinctual tendency to avoid mating with different species to ensure we have strong and healthy offspring.
I already have an answer discussing this, so I won't go into it more. Short version though, remember that mating between races will be a lot less common than fantasy stories generally imply. Also remember this DOES NOT require racism, this can be instinctual and not even recognized tendency.
