Thx to jaeyson. You saved my day after running into the same problem and trying one deploy after another 
.
To give an additional info: until recently if someone creates a new phoenix project and starts fly launch the release files were built as expected. Now, it seems that if you just use fly launch the ecto part release files (rel/overlays/bin/migrate and rel/overlays/bin/migrate.bat) are not built by default and therefore missing.
So, as jaeyson wrote, run mix phx.gen.release --ecto before running fly launch.