That's a definitely acceptable size, thanks for pointing that out. Yeah a bunch of symlinks should solve the issue. If the binary is kept cached in RAM at least, there should be no overhead in starting it. I think it's pretty rare to have environments that are so memory constrained that they can't hold onto 8 MB of RAM.
Note that not all targets are that small though. Musl has indeed 8.3 MiB, but in coreutils-0.0.12-x86_64-unknown-linux-gnu.tar.gz, the size of the coreutils executable is 12.6 MiB. On the bright side, on the same target, a local build with the cargo features to reduce bloat enabled gives only 7.1M. All these numbers are acceptable.
That doesn't seem so bad, the GNU coreutils Debian package has an Installed-Size of 17.9MB. Though there might be hidden drawbacks I don't know about.