Normally, when there's an ongoing police investigation, the police can either request and retain a copy of the data, or request the holder of the data retain it until "further notice". I'm assuming that's what was going on here.
"If he was, I'd argue the dragnet-collected evidence is only circumstantial."
The phone logging was not conclusive evidence, only used to establish that he had been in the area. They found various artifacts in his house, like a roll of duct tape with the dead girls DNA on, that he explained he had found while walking around the lake, the same type of duct tape used to bind the girl. They also found various other items with the girls DNA on.
They used the logging data to establish his whereabouts for the night in question and compared it to his statement of where he'd been. They also used various financial transactions, like buying a cup of coffee with his credit card at a gas station, etc.
In Denmark, DNA cannot be used as a single evidence, only as supporting evidence, and the same goes for phone logging. But combined, if your location data says you've been there, and your DNA is found at the crime scene, even though it may not by itself be enough to get you convicted, it makes all other evidence much more believable.