The Latin prefix for “with” was con-, but like other Latin prefixes, its final consonant changed to match the following consonant. So com-pare, col-late, cor-rupt. The prefix in- does the same: im-port, il-literate, ir-relevant.
Now, another variant of con- was co-, before h and vowels: co-herent, co-agulate. English generalised this version of the prefix into a new version of the prefix, which did not care what letter followed it (so long as you use a hyphen). So if the notion of co-dependency had been invented 200 years ago, it would have been condependency, because the co- prefix had not become generic yet.
So it’s spelled cor-related rather than co-related, simply because it is an older word.