In a nutshell: Your explanation is correct. Mutual interdependence would be redundant.
Mutual dependence = interdependence :)
There are numerous phrases and popular sayings in English that simply don't make sense when subjected to any kind of thoughtful analysis, such as "irregardless," which is said far too often in American media (and it's not even a word), or "overexaggerate" (also not a word). Both of these are examples of redundancy, just as your example was. People often try to sound smarter than they are by using such terms, and in doing so incorrectly, expose themselves to be frauds.