I've experienced what you are talking about. The direct cause, as often happens with such 100x slowdowns, is that the software starts swapping to disk (extensively using scratch files in case of Photoshop). So essentially yes, this is a memory issue.

You can check for it by purging the undo cache, or just saving the work and continuing after restarting Photoshop. The problem usually kicks in after some edits. (Every stroke you do with a brush saves the whole tile under it. By the way, you can try to adjust the History & Cache settings, reducing the tile size for extensive touch-up edits). Also, you should see and hear your hard drive working every time you touch the brush when the problem happens.

In any case, your CPU and esp. GPU are practically above suspicion: they are more than sufficient for 'normal' Photoshop work. With memory usage, though, Photoshop (and Adobe in general) are quite... liberal, and it helps to have more.

(Needless to say you must be using the 64-bit version to utilise that memory, even your current one).

There is a (kind of) alternative though, and it's worth considerinig both. If it has to swap (and with a large enough job, it will eventually), you may want to invest in a fast drive for scratch files. That is, a small (128-256 GB), cheap and fast SSD. It costs much less than 8 GB RAM today, and it can make the slowdown like 10x rather than 100x, which may be at least bearable.

Due to nature of SSD, it wouldn't be wise to use it as a system drive, so the best configuration today (IMO) is to have 2 SSDs: the best, most reliable but not necessarily the fastest one as a system drive, and any cheap one for scratch/temporary files. Plus a large HDD (or NAS) for actual storage.

But of course, if you have to choose, do get RAM first.