I had been using Mycelium which is also known for more than appropriate fees. So all in all I think I did pay more than sufficient fees for the transaction.
Well, I can't change the past now so be it. I guess I'll just import the seeds to a different wallet now.
Enough of Mycelium already.
There is no point in using a wallet, if it doesn't allow you to set a fee as per your liking. Bitcoin is a completely decentralized asset and users can set the fee to any level they want. You can even set it to 0 Sat/Byte or 1 Sat/Byte. Now the wallets can't dictate how we set the fee. If they impose any minimum limit on the fee, then it goes against the spirit of Bitcoin. There are a lot of wallets available which allows you to set the fee by yourself. So there is no point in continuing to use Mycelium.