Place the phone somewhere where you literally have have to stumble oversee it on your way out.
One such place is the door handle of the cubicle / toilet. If there's an old-fashioned handle there, you can carefully lay the phone on top. Now it's impossible to forget your phone.
But not all toilets are build that way. You can:
- Lay the phone on top of the toilet paper dispenser (if it has a horizontal top)
- Lay the phone over (or right next to) the button to flush the toilet
- Lay the phone on the floor right in front of the door (if the floor is clean). If you have a booklet-style phone case, you can stand it up like an open book to minimize the area that comes into contact with the floor.
- Balance the phone on the top of your shoe or put it in your shoe like an ankle knife.
- Just hold it in your non-dominant hand