This pattern seems to go all the way back to Proto-Indo-European.
As Sumelic pointed out in a comment, we actually see this same alternation in English: when~then, what~that, where~there, and so on. This wh~th alternation comes from older Germanic *hʷ~*þ(*), which comes from PIE *kʷ~*t by Grimm's Law (which weakened stops into fricatives at the beginning of words).
(*) þ ("thorn") was probably pronounced like English "th" in "thin", IPA /θ/
It seems like the former ones come from PIE *kʷi-/kʷe-/kʷo-, the interrogative-indefinite pronoun (surviving as quis in Latin and tís in Ancient Greek); the latter ones come from PIE *to-, the neuter demonstrative pronoun (the second half of iste in Latin, the definite article tó in Greek).
Various suffixes were added to derive specific meanings, like "which time" or "which quantity", and the forms with these suffixes turned into the qu-~t- pairs. It's not always clear what these suffixes were; for example, the second half of quālis~tālis can only be guessed at. But the roots themselves seem clear.