but I already tried atof()-commands and they all failed as well.
No. The failure is on your part. A double on the Arduino is the same size, and precision, as a float - 4 bytes. A 4 byte float has a precision of 6 or 7 decimal places. Expecting better than that is a mistake.
For that I submit GPS-destination-coordinates like "12.12345678" via Serial Monitor to my Arduino Mega 2560.
That value is a combination of degrees, minutes, and seconds. You could parse that string (as a string, not as a double) to get degrees, minutes, and seconds. You could parse the GPS string (as a string, not as a double) to get degrees, minutes, and seconds. You can not expect seconds to 5 decimal places, though. You could then write your own functions for getting distance based on degrees, minutes, and seconds.