Stroke appears around each individual shape despite merge paths

[Pascal5D73]

I had 3 separate shapes (Egypt, Sudan and South Sudan) and I wanted to merge them into one shape, so I copy pased them into an empty layer. After that I added "Merge Paths" so these indiviual shapes would become one. When I added a stroke however the stroke wasn't only on the outside of the new shape but also appeared where the indiviual shapes touch eachother. Basically the stroke was treating them like individual shapes and not like one shape, despite the use of merge paths.
I made sure to select "merge" for the mode, not "add" or any of the other options.

How do I get the stroke to appear only on the outside of the new, merged shape?

Here's a screenshot of the layer and the preview:

[Mylenium · Accepted solution]

Merge paths operates on intersecting shapes, which borders on a map are not. What you want will require to actualyl combine the shapes in Illustrator and import them as a single shape or the other way around to duplicate your shapes and delete the inner borders in order to apply the stroke only the left over contours. None of this even requires a Merge Paths, so get rid of it.

Mylenium

[Pascal5D73]

That solved my problem, thank you very much!

[Pascal5D73]

What solved the problem was to combine them in Illustrator.
However, I was wondering about the other method. How do I "delete the inner borders"? 
By breaking the path open and just delete the path points with the pen tool and then connect the end points of the shapes with each other?