Does the fragment "almost impossible to underestimate" make this sentence illogical?

Solution 1:

This is an interesting phrase because, depending on how you read it, it could mean exactly the same as its opposite.

It's almost impossible to underestimate the importance of these movies

= these movies are so important that to underestimate them is, quite simply, impossible.

It's almost impossible to overestimate the importance of these movies

= these movies are so important that no amount of overestimation is too much.

"Such and such can't be overstated" is similarly ambiguous. In the same way, it could mean the same thing as "Such and such can't be understated."

Solution 2:

You are right that the fragment is illogical. There is a full discussion of this at Language Log: Misunderestimation

Solution 3:

The Language Log post that Shoe pointed out also refers to an earlier post on Overnegation, as the topic is called.

For those interested, here's a fascinating handout, with examples, from a recent paper on the subject by Larry Horn, who is the expert on English negation. As it turns out, logic is a weak reed to lean on with potent operators like negation.