why does this custom exist? Why does one adopt a new name when he/she becomes a monk/nun - why will the birth name be removed for the rest of his/her life?
The custom to take a new one for the religious life was very usual (I'm quite sure that it was mandatory, at least in some orders) until the Second Vatican Council, as Anneza pointed.
It was a sign of renonce to previous civil life and an external mark of a new identity, as other signs which has been abandoned too: the tonsure for priests and monks and to crop the hair for nuns, for example. The same kind of change of name as external sign of new identity and life appears in other fields: arts and music (Prince, e.g.), BDSM (submisive/sub or slave's name, e.g.), conversion names...
The change of name is not longer usual, but it is still in some cases, specially when the civil name is not very religious or among strict orders. I know the case of a girl named Samanta who recently toke her perpetual votes as nun in a strict order (I will ask my in-laws which one and I will clarify here later) and toke the religious name of Sor María de la Cruz (that is only her religious name, her civil name is still Samanta Paternal family name Maternal family name).
And is this also legal? I mean, wouldn't a new nun or monk have to change her/his legal papers since she/he assumed a new identity?
No, it is not legal, at least in secular Western European countries.
Or is this one of those things where church and the law are still separated?
Yes, Church and law are two different things, at least in Western European countries; religion is only a private matter. If a nun/a priest/a monk wants to legally change her/his name, it is possible but only as any other person who wants to change her/his name and she/he has to follow the legal process to make it (then, the change could be allowed or denied).
But, in any case, the legal change of name will only affect the given name(s), never the surnames.