Obviously we are dealing with two different roots here: Scheidung (from scheiden) and Trennung (from trennen). The additional modifier Ehe- is simply a compound component and clarifies that it is the divorce of a marriage you are talking about, which also makes Ehescheidung much more of a technical and law term.
According to the etymological dictionary entry shown on DWDS.de, trennen — while nowadays simply meaning to part — originated from a root closer to to flee. In modern usage, it has taken over most of the meaning of the other verb scheiden, which originally meant to separate.
The old meaning of to separate is still very present in the word Scheidung which is nothing short of separating the former maritial bond between to people. Scheidung is recognised as exactly the nullification of a marriage, so it implies having been legally married and legally no longer being married.
On the other hand, Trennung is a much broader term. As mentioned, it has taken over the general meaning of separation from the original word Scheidung — and that is exactly what it describes, the physical separation of what was once close or together. There is no necessary implication of marriage; instead ending any relationship is termed Trennung and some even introduce weird (to me) concepts like Trennung auf Zeit — separation only for a limited time.
In Germany, a Scheidung always has an implied previous Trennung. For a marriage to be declared divorced, the parties have to ‘separate bed and table for a year’ — commonly interpreted as having lived apart for at least a year.
While I have used the term marriage consistently and I believe German law would do so, too, I would also use Scheidung if I wanted to imply a registered homosexual partnership officially nullified. Note that these are not officially called Ehe (in spite of the colloquial Homo-Ehe) and thus this divorce cannot be termed Ehescheidung in legal contexts.