sign out of all of your Edge browsers (stable, beta, Dev etc) and only stay signed in on one of them.
on that browser where you are still signed in, delete all of your favorites and keep the browser open to complete sync. give it some time, like half an hour.
after that, start signing into other browsers (still don't touch Android) and see if all of the favorites are properly deleted, you shouldn't see anything when you go to: edge://favorites/ in any of your Edge browsers.
once you are sure that your favorites are deleted, sign out of All of your browsers. (at this point your Microsoft account is not connected to any instance of Edge browser)
now go to Edge on your Android, sign in using your Microsoft account, keep Edge open and let it sync data back to the cloud servers.
after some time, start signing into other instance of Edge (stab, beta, dev etc), one by one, with at least 15 mins delay between each sign in.
do all of these steps, one by one, and then report back the results. I'm confident that it will fix your issue.