The most likely explanation is they sent her a message saying pseudonyms are not allowed, and asking for her real name. She replies something like 'My real name is XYZ, here is ID to prove I am a real person, but I do NOT wish to use that name, please continue to call me ABC on the site' but Facebook simply went ahead and changed her name from ABC to XYZ against her wishes. No secret data mining, information collection or machine learning required.
One explanation is that Facebook collects its users contact lists.
That way, it can create 'shadow-accounts' for people that don't have yet a Facebook account. So when/if that person finally creates a Facebook account with some data tying him/her to a shadow-account, Facebook can directly propose relevant contacts and already knows a lot about that person, including his/her real name.
This doesn't suprise me at all. Big data-hungry companies like Facebook or Google know A LOT about you. I'd say they even know a lot of things about their used that their used don't even know about.
I'd be very surprised if Facebook didn't know my parents' names, my kids names, my shoe size and any other piece of information I haven't provided explicitly.
Just assume that anything that you entered on any website, or that you mentioned directly or indirectly to anyone on Facebook is available to Facebook.
In the creepiest of worlds I imagine this: on a non FB website with a FB "share" button on it, I congratulated a friend on her birthday five years ago. When she gets a FB account for the first time tomorrow, Facebook already has her shadow account with good Guesses of her details, including the birthday and real name.