Does the lead need to be created right after form submission in order for GA Connector to add tracking data to it?

Fortunately, no.

Your lead can be created within two weeks. As long as the lead’s email address matches the form submission email address, GA Connector will add the tracking information to it.