help me build a Major 15,000+ LED Arduino application project

I don't think the deadmau5 wall is a simple LED hack. It looks to me like a matrix of jumbotrons, which are LED based, but have lots of proprietary circuitry. A 33 ft. x 110 ft. jumbotron costs about 3 million dollars today.

In terms of "doing it yourself" I think you may eventually run into problems of scale. You need 16 digital outputs to control an 8 x 8 matrix of LEDs... The Arduino Mega has 54 digital I/O pins so you can get at least 3 matrices running on a single board... 192 LED soldered, only 14,808 to go!

For a wall of that size, do you need that much "resolution"? For example, I have seen quite a few "LED walls" made with a matrix of frosted glass blocks. Each glass block only requires one LED at its center. The light illuminates the whole block evenly. Using a technique like this you would need to use significantly less LEDs, and could probably get away with only using 3 or 4 arduinos.

How long will this wall be up for? Personally, I usually lean towards projection/projection mapping instead of a huge LED matrix for big installs... if its a short engagement, look into renting a high-lumen projector... or, if you are trying to do this on the cheap, use something like Dan Shiffman's open source "Most Pixels Ever" library (written for processing) so you can stitch a huge visualization across a collection of inexpensive LED projectors.

http://code.google.com/p/mostpixelsever/

As for your other question, your digital video is already an array of values so you have lots of options routing that data to an LED matrix... lots of folks use max/MSP/Jitter, many use processing, you could even do it in flash... it all comes down to how you wind up wiring your lights up and the language you are most comfortable programming in.