Technically a small piece of paper is worthless - having zero resale value, so why is the saying not: It is worth the paper it's printed on?
“Not” in comparative forms typically means “less than”. For instance,
I’m not as tall as Michael Jordan.
means “I am less tall than MJ”, rather than “I am not exactly the same height as MJ”.
So in this case, “it’s not worth the paper it’s printed on” (and parallel constructions like “it’s not worth waiting ten minutes for”), not means it’s worth even less than the paper is — and that’s already a negligible amount. So it means something is worth a really really negligible amount — or even, as @Martha suggests, worth less than nothing.
Because you're trying to say precisely the opposite. It is so worthless that its worth is not even superior to that of the paper on which it is printed. It's a little misleading to compare value, because even though you're quantifying the worth of something to something else, you're implying that the worth is at least that much (even if it is not actually said). An example of this would be "Even though that sweater cost me 100 dollars, it was worth it." Even though you're saying it's worth 100 dollars, you're implying that it is at least worth 100 dollars.
So the opposite of saying that it is worth the paper it is printed on is saying that the worth does not even exceed that of the paper it is printed on.