Your Instant App APKs contains an APK that is greater than the maximum size of 4364793 bytes

I was a little thrown off by the message "APK contains an APK", thinking that you might have some exotic app. But I don't see that string in the publishing code, so I think you're running into a more typical error.

The Instant App format is a ZIP file containing APKs. Each of these APKs must be under 4MB.

Additionally, if your app is split up into feature APKs and a base APK, then any combination of feature + base must also be under 4MB.

If you use configuration APKs, then those also contribute to the limit, but I don't think you are.

Off the top of my head, I'm not sure what APK Profiler is telling you for instant apps, whether it's the size of the whole ZIP, or of a single APK. I could be wrong, but I don't think it knows about the calculation of our 4MB limit. One easy way to check the sizes without using any fancy tools is to just unzip the ZIP file and look at the sizes of the APKs on disk. Or use APK Analyzer.

One other thing: if you publish to dev track, there are no size restrictions there. Not that that solves your size problem, but it can be a useful way to play around with Instant Apps before tackling the size problem.

Source: Instant Apps FAQs: App size.

4MB is the designated size limit of Instant Apps in Android as stated in the documentation:

You must be mindful of the 4MB size limit for instant app downloads. Also, each feature needs to have a single activity as its entry point.

What I can suggest is that check the Reduce APK Size docs. Its suggests removing unused resources, minimize resource use m libraries and so much more.