Hey, I've been building the Swift toolchain natively on Android and ran into some similar issues before. I had the same problem with linking against the full path to the shared library when the soname for the library wasn't set, maybe that's affecting you somehow. readelf -d libswiftCore.so | grep SONAME will tell you if the soname has been set: compare with the result for other working Swift libraries to see the difference.
Another issue that might affect you is that Android uses DT_RUNPATH and actually enforces it, ie every shared library must list its shared library dependencies explicitly. This can give you cryptic errors in a dependency tree, where it errors because it can't find libFoundation.so, but you're confused because the library libFoo.so that you're linking against clearly lists that dependency and its RUNPATH. But if libFoo.so depends on some other library libGoo.so that doesn't have the RUNPATH for Foundation set properly, that might really be the one causing the problem: the dynamic linker error simply won't tell you which library is missing its dependency.
As for building libicu for Android, I use the Termux package for that. You can download the binary package and unpack it or build it from source yourself. The only issue is that it's built against Android API 24, so you will have to build the Swift SDK for Android with that API too.
If you have any questions, let me know.