A phone recording surviving the crash isn't too implausible. Remember that it doesn't need the whole phone to come through in one piece, only the memory chip (possibly an SD card).

On the other hand, the reason I'm very skeptical about this story is this part: "Near the end there was reportedly a heavy shake and the cabin tilted sharply to one side. After further screams the video ended, Bild said."

The impact speed has been estimated at about 700 km/h, or about 200 metres per second. The fuselage of an A320 is 37 metres long. First impact to complete destruction would take about 1/10 of a second; the described sequence of events takes far too long to be plausible. (The only way it might work is if the first impact was on a wingtip.)

"but French police say story is false" ... ""Considering that everything on the plane was destroyed, it would be unusual for a mobile phone to survive the impact""