How we change what others think, feel, believe and do
Explain that you need to go to the toilet.
You can signal this by twitching subtly beforehand (do not overdo this!).
Look slightly embarrassed to be asking to be excused and they will hurry to give you 'permission'.
There are many ways of talking about the toilet in a socially acceptable way, ranging from polite euphemisms to bold humor, -- use one that suits the situation.
Er..sorry, I need to go to the toilet.
Excuse me -- I need powder my nose.
Back in a mo. Just going to point Percy at the porcelain!
Declaring yourself embarrassed places the other person in a position where they are complicit in causing that embarrassment. They will thus of course escape further embarrassment as quickly as possible and be pleased to see you leave.
When you desperately need to go to the toilet, you simply have to go, so even if they are not embarrassed with you, there is clear social precedent that you can simply go.