I fixed it the following way,
- Setup Domain in Cloudflare
- Setup Fly Ip addresses in Cloudflare
- Setup Cloudflare as Full SSL Mode
- Make records pass through only
- Generate Certificates
- Turn DNS Proxy back on
Since Fly needs to verify the ip address during certificate issue, I think this would pose a problem when the certificate expires. Is there any way to mitigate this, would setting up that optional CNAME for ACME verification help ?