An 800x600 image is just under half a million pixels. The magic wand takes about 5 seconds, which is not too bad. A 1024x1024 image is just over a million pixels. With double the pixels you might expect it to take about 10 seconds. It actually takes about 60 seconds. The 2048x2048 image is just over 4 million pixels, and I got bored waiting for it to finish.
The photo I found the problem was 20MP but not as bad for performance as the random noise. Selections with the magic wand were taking over a minute though, which is a right pain when you want to play with the tolerance to find a value