You can do this in any audio sequencer/recorder. you could use industry standard software such as ProTools, Cubase, or something along those lines but you could do it equally as well with cheaper software such as Tracktion. As long as you can import/export and edit the audio (i.e. cut, paste, glue) then you will have no problems. The mashup you posted is really basic compared to the MTV mashups because only the vocals have been edited.
What this person has done in particular with this mashup is:
1) They've taken the backing track for innocene
2) They've taken the acapella for crush
3) They've imported both audio files into a sequencer on two seperate tracks
4) They havn't edited the innocence track
5) They've edited the acapella for crush (i.e. cut and alligned sections to fit over innocence).
I've never used acapella so I wouldn't know whether it's possible to change the tempo, but from hearing it, it sounds as if the tempos been reduced on crush to fit with the original tempo of innocence. You've gotta know how to use the sequencer your editing in because you'll be doing a lot of fine editing. Download Audacity or the free version of Ableton Live and see how you get on, if you enjoy it then you could upgrade to some better software.
Keep me posted on how you get on, i'd like to hear what you put together
