This is embarrassing, I did not remove the module from the circuit and the timepulse output goes to a PIC input. I powered only the GPS module but I guess the PIC was trying to run from the PPS signal through the clamp diode and was loading the PPS output. Once I cut the trace to the PIC, the output is clean.
Ublox specifies the PPS accuracy to 500ns indoor and 20ns clear sky. That correspond to 500ppb indoor and 80ppb clear sky by my calculations. That is not bad at all, it beats most free running oven oscillators and definitely enough to verify almost any instrument.
Yes, FLL is frequency lock loop and is exactly what you describe, for example accumulating the counts over 16 seconds and correcting the oscillator to get an expected number.