Calculating fee based on fee rate for bitcoin transaction

I’m writing an algorithm for calculating fee based on fee rate and amount to be sent (requested amount) in order to propose the fee to user;

1. Sorting UTXOs ascending based on value
2. Take enough UTXOs so sum is larger than requested amount
3. Calculate change, add to outputs
4. Build tx
5. Calculate fee based on tx byte size times fee rate
6. Is Change larger than calculated fee? (can we "fit" fee into change)
7. If no: go back to step 2 and add more UTXOs to get to fee
8. If yes: reduce the Change for fee and build final transaction

This works well in most cases, but if you have large number of UTXOs with small values and fee rate is large (e.g. 88 sat/byte), you can end up with very large transaction, i.e. very large fee for sending very small amount of coins.

I have tried to make a change in algorithm where after X number of iterations, I would give up and try to take enough UTXOs for requested amount and deduct fee from that amount and send what ever is left.
But I ended up in long loop again, as UTXOs were small, transaction large and in every iteration I didn’t had enough to pay the fee.

As this is obviously bad implementation, is there any other way to calculate fee bases on fee rate?