I'll separate them into groups of three or four and hand shuffle each until I mentally lose track of their order. Then I put them together and start grabbing two or three and re-inserting them. At times I'll take one off the top or bottom and stick them in somewhere in the middle. Then a thrilling finish by shuffling one or two more times again.
When its time to make my dungeon stack of the required fixed number of tiles, I'll take one from the top, middle, near the end, near the top, a couple in order until I get the count I need. By this time I have no idea what is where and place the rest aside.
To me, the bottom of the dungeon stack is the top of the "leftovers".
I tend to split them into 3-4 stacks which I shuffle, then I combine them into one tile stack by grabbing a few from each stack at a time. It's probably not perfectly random this way but it's not like it needs to be.