Why does everone say Apocolapse is Immortal? He really isn't...he has to change bodies after they age and are unable to contain his power. Doom wins this one with prep(simply build a device that speeds up the aging process within Apocolapse's host body). Without prep, and i hate to say this, but, Doom wouldn't be able to destroy Apocolapse, but on the same hand I doubt Apocolapse could destroy Doom.
Here is a site that I found that has info on these two great marvel villians.
Doom or Apocalypse?
Pro Doom
It depends whether or not Doom knows anything about Apocalypse and his reliance on host bodies.
Anti Doom
If Doom has no info on what does harm Apocalypse then Doom is out of luck.
Doom has magic, however is Doom's sorcery such that it would be successful in beating Apocalypse. I'm not so sure considering. Selene is very powerful with magic and if you remember the External fiasco she didn't even bother with Apocalypse.
Pro Apocalypse
Apocalypse most likely has info on Doom so this would be a major advantage on his part.
In addition, Apocalypse's control over his atoms are so vast that he could achieve internal nuclear fusion, or becoming extremely dense that he could not be physically harmed.
For people that say Doom is more intelligent than Apocalypse where is your basis for this. Sure Doom is highly intelligent like taking Galactus and Beyonders powers. However, all he had to do was figure out a way how to absorb cosmic energy.
But, Apocalypses powers consist of transmogrification and being able to alter his atomic structure. An ability so rare it left Uatu almost dumbfounded.
Anti Apocalypse
If Doom does know of Apocalypses need to constantly get new host bodies than he may be able to find a way to rid the world of Apocalypse. One way could be magically removing his essence while Apocalypse is in a physically weakened state.