I have a somewhat different perspective than the two more Qabbalistically inclined answers.
I know this is unpopular, but "tahor" really does mean purity. Just not with the connotations of "spiritually impure" that speakers who insist it doesn't are trying to avoid. For example of a clear use of "tahor" as purity, the menorah must be made of "zahav tahor" (Shemos 25:31); the word for the purity of gold is "tahor". So the question is what is the substance we don't want adulterated, and what is the "dross" we don't want that "gold" to be adulterated by?
The Ramchal (Mesilas Yesharim, ch. 16) defines the personal attribute called taharah:
Taharah is the correction of the heart and thoughts... Its essence is that man shouldn't leave room for the inclination in his actions. Rather all his actions should be on the side of wisdom and awe [for the Almighty], and not on the side of sin and desire. This is even in those things which are of the body and physical.
To the Ramchal, taharah is purity of the "heart and thoughts". The the tahor man has "no room for the physical." It is the purity of the deciding mind from the physical creature.
To cast the words of the Ramchal into the terms we discussed in the introduction, taharah and tum'ah focus on the relation ship between the physical and the mind. Taharah is the purity of the mind from physical prejudices. Tum'ah is its adulteration, so that the decision making process can not be freed of the physical urges.
This is mussar's description of a personality trait called "taharah."
To answer my opening questions, it seems that taharah is the purity of the mind and of free will from the pernicious belief that we are nothing more than physical beings and puppets of our physical drives.
And halakhah's concept seems to derive directly from it. Look at how Rav SR Hirsch (Commentary on Lev. 11:47; sorry, I couldn't find an on-line copy) describes the tum'ah of a dead body:
A dead human body tends to bring home to one's mind a fact which is able to give support to that pernicious misconception which is called tum'ah. For, in fact, there lies before us actual evidence that Man must -- willy-nilly -- submit to the power of physical forces. That in this corpse that lies before us, it is not the real human being, that the real human being, the actual Man, which the powers of physical force can not touch, had departed from here before the body -- merely its earthly envelope -- could fall under the withering law of earthly Nature; more, that as long as the real Man, with his free-willed self-determining G-dly nature was present in the body, the body itself was freed from forced obedience to the purely physical demands, and was elevated into the sphere of moral freedom in all its powers of action and also of enjoyment, when the free-willed ruling of the higher part of Man decided to achieve the moral mission of his life;
R. SR Hirsch portrays the tamei object as one that causes the illusion that man is nothing more than a physical object, an animal, a helpless subject to physical forces and physical desires. In reality,
death only begins with death, but that in life, thinking striving and accomplishing Man can master, rule, and use even his own sensuous body with all its all its innate forces, urges, and powers, with G-d-like free self-decision, within the limits of, and for accomplishment of, the duties set by the laws of morality; ...
"Thinking striving and accomplishing Man," the conscious man, should use the "sensuous body with all its innate forces, urges, and powers," the physical man, as a tool for doing good. The object which halachah calls tamei is that thing which will cause mussar's tum'ah to awaken itself within the mind. It becomes a self-fulfilling prophecy. The mind that is prejudiced by physical needs and urges can not fully choose its own destiny.
Since the tamei is that which reinforces the idea that man is a being of mere physicality, tum'ah is only associated with the dead bodies of animals "whose body-formation is similar to that of Man, primarily the larger mammals." The shemonah sheratzim, the only smaller animals that are tamei, are vertebrates "that live in the vicinity of human beings," the weasel, mouse, mole, etc... All these are animals we see about us, living much as we do. The animals that closer resemble man have stricter rules of tum'ah. Similarly, menstruation and sexual emissions, which also cause tum'ah are things that happen to man, unwittingly, "willy-nilly submitting to the power of physical forces."
In contrast, to become pure we immerse in a miqvah. The root of "miqvah" is ambiguous. The straight-forward definition would be "a gathering of water," which a miqvah is in a very literal sense. But the word can also be read "source of hope." Perhaps (my own suggestion) this is an allusion to the idea that it provides us with the faith that we are not mere creatures of the laws of biology, but can rise above those laws to master our own fate.
As for its relationship to qedushah.... I have a longer discussion in my book (Widen Your Tent, sec. 3.5: "התיחדות — Being Set Apart"). In short...
Both taharah and qedushah derive from havdalah (separation). The key to the difference is looking at which preposition is used after each. Someone becomes "tahor mei- / tahor from..." Whereas qedushah is always "qadosh le- -- separated for", or "consecrated". Such as the tzitz (gold forehead plate) of the kohein gadol (High Priest) reads "Qadosh Lashem -- Consecrated to G-d". And at a wedding, the groom declares "Harei at mequdeshes li... -- You are hereby separated to be fpr me..."
Taharah is a precondition for qedushah because I cannot commit myself to do my mission in life until I get myself disentangled from and deal more objectively with those things that pull me down.
And since this is true of the middos of taharah and qedushah, it is also true of the halakhos of objects, places and activities that are set aside by halakhah because they tend to cause tum'ah or qedushah in one's character..