The most likely explanation here is that Google was conducting its own investigation into Russian disinformation and discovered the suspicious search queries. They then turned the anonymous query records over to the FBI with the understanding that they would then generate the necessary court order to request Google de-anonymize them. That is why the second sentence explicitly says "records from Google."

I've done this dance before. It is the cleanest way to turn over evidence of a crime that is discovered in a private investigation.