Hi,
If all is well (both at Fly’s end, and Let’s encrypt’s) it should be seconds/minutes 
But … I recall adding Cloudflare in to the mix adding complexity because (naturally) it intercepts the requests and so does not return the expected A/AAAA values. As you describe, the solution should (in theory) be to add a sibling non-proxied (aka grey cloud) record which has the acme challenge value. That should be sufficient to pass the validation.
However it may be complicated if using an apex domain. I’m not sure if you mention mydomain.com for brevity or whether it’s an actual apex but there may be a difference between requesting a cert for:
example.com
*.example.com (ie a wildcard one)
www.example.com (specific subdomain).
… at least based on the numerous replies to this thread. I recall a while back that e.g www.example.com proxied (orange cloud) behind Cloudflare (with the sibling non-proxied acme challenge record) was near-instant … but using e.g example.com with the same setup wasn’t:
Perhaps someone who has done it more recently will have more knowledge