Why is “chmod -R 777 /” destructive?

First of all a minor terminology nitpick: chmod doesn’t remove permissions. It CHANGES them.

Now the meat of the issue — The mode 777 means “Anyone can read, write or execute this file” – You have given permission for anyone to do (effectively) whatever the heck they want.

Now, why is this bad?

1. You’ve just let everyone read/modify every file on your system.
   • Kiss password security goodbye (anyone can read the shadow file and crack your passwords, but why bother? Just CHANGE the password! It’s much easier!).
   • Kiss security for your binaries goodbye (someone can just write a new login program that lets them in every time).
   • Kiss your files goodbye: One user misdirects rm -r / and it’s all over. The OS was told to let them do whatever they wanted!
2. You’ve pissed off every program that checks permissions on files before starting.
   sudo, sendmail, and a host of others simply will not start any more. They will examine key file permissions, see they’re not what they’re supposed to be, and kick back an error message.
   Similarly ssh will break horribly (key files must have specific permissions, otherwise they’re “insecure” and by default SSH will refuse to use them.)
3. You’ve wiped out the setuid / setgid bits on the programs that had them.
   The mode 777 is actually 0777. Among the things in that leading digit are the setuid and setgid bits.
   Most programs which are setuid/setgid have that bit set because they must run with certain privileges. They’re broken now.
4. You’ve broken /tmp and /var/tmp
   The other thing in that leading octal digit that got zero’d is the sticky bit — That which protects files in /tmp (and /var/tmp) from being deleted by people who don’t own them.
   There are (unfortunately) plenty of badly-behaved scripts out there that “clean up” by doing an rm -r /tmp/*, and without the sticky bit set on /tmp you can kiss all the files in that directory goodbye.
   Having scratch files disappear can really upset some badly-written programs…
5. You’ve caused havoc in /dev /proc and similar filesystems
   This is more of an issue on older Unix systems where /dev is a real filesystem, and the stuff it contains are special files created with mknod, as the permissions change will be preserved across reboots, but on any system having your device permissions changing can cause substantial problems, from the obvious security risks (everyone can read every TTY) to the less-obvious potential causes of a kernel panic.
   Credit to @Tonny for pointing out this possibility
6. Sockets and Pipes may break, or have other problems
   Sockets and pipes may break entirely, or be exposed to malicious injection as a result of being made world-writeable.
   Credit to @Tonny for pointing out this possibility
7. You’ve made every file on your system executable
   A lot of people have . in their PATH environment variable (you shouldn’t!) – This could cause an unpleasant surprise as now anyone can drop a file conveniently named like a command (say make or ls, and have a shot at getting you to run their malicious code.
   Credit to @RichHomolka for pointing out this possibility
8. On some systems chmod will reset Access Control Lists (ACLs)
   This means you may wind up having to re-create all your ACLs in addition to fixing permissions everywhere (and is an actual example of the command being destructive).
   Credit to @JamesYoungman for pointing out this possibility

Will the parts of the system which are already running continue to run? Probably, for a while at least.
But the next time you need to launch a program, or restart a service, or heaven forbid REBOOT the box you’re in for a world of hurt as #2 and #3 above will rear their ugly heads.