Nietzsche believed epistemology to be subordinate to knowledge of the will and its struggle, while phenomenology made no claims regarding knowledge beyond the subjective experience. So they both dealt with their subjects as one would expect from a consistent subject-based philosophy and did not stray from them to make claims about the alleged falsehood of objective rational thought. As further example, Nietszche still believed rational and scientific knowledge to exist - he simply claimed it was merely a form of the will to power manifested as will-to-knowledge.
The problem that is quite specific to po-mo is its willingness to assume it has overthrown the ideas that went before it when it has not actually done so and when it is never able to provide any decent arguments as to how it believes itself to have done so. Indeed, to understand much of po-mo it is necessary that you first accept on faith the idea that the "old ideas" have been overthrown, after which one can proceed by means of non-logical arguments to prove with absolute certainty that proof and certainty no longer exist. Eventually, you end up with Lacan, desperately clinging to the semblance of certainty and authority that mathematics represents, wrapping his sham concepts up in mathematical-analytical pseudo-equations, even as his creed pretends to spurn such analytical certainties and methods. All very bizarre...