"Él corresponde con ella."
Translation:He corresponds with her.
"He writes with her" would only be used in English if 2 people are writing an article together or a book, etc.
'He corresponds with her' relates to the fact that he writes to her and [it is implied] she writes back. 'Correspondence' is still use to refer to the act of writing to each other, at least in a court of law!
I thought this as well; but, it seems the literal definition is to write together?