I've just finished the (great) game, and I think I only missed two of the Sokolov paintings. I'm also pretty sure to know the chapter where I missed them; can I simply reload this chapter and collect the missing ones, or should I replay the entire game ?
Ok, so after several tests, it appears that yes, this achievement has to be earned in a single playthrough.
Also, I had a little problem with Granny Rags: during my second playthrough to get all the paintings, I ran as fast as possible, skipping almost all the side quests, including Granny Rags ones. It prevented me from getting the last painting ("The Outsider and the Circumstanced Void"). As a matter a fact, when you skip her quests, you cannot access one of the last areas where you can either fight her or help her to kill Slackjaw but also access her room where you'll find the painting. So that's something you'll have to keep in mind if you start a playthrough dedicated to the paintings.