As explained in the Wikipedia article on self-determination you link:
Most sovereign states do not recognize the right to self-determination through secession in their constitutions.
(And this includes Spain.) The key words here being "through secession". There's an obvious tension between territorial integrity (a cornerstone of international law) and self-determination through secession. So the better question is how comes sometimes we see results like Kosovo:
Kosovo unilaterally declared its independence from Serbia on 17 February 2008. Since then, its statehood has been recognized by 69 countries, including the United States and most European Union nations. Serbia and Russia are among the majority of States rejecting its independence. Serbia sought international validation and support for its stance that the 2008 Kosovo declaration of independence is "illegal" at the General Assembly. On 8 October 2008, the General Assembly of the United Nations adopted resolution 63/3 in which, referring to Article 65 of the Statute of the Court, it requested the Court to render an advisory opinion on the following question: “Is the unilateral declaration of independence by the Provisional Institutions of Self-Government of Kosovo in accordance with international law?” [...]
The Court further found that previous condemnations by the Security Council of unilateral declarations of independence had to be seen in their specific context noting that the illegal character of those declarations stemmed from the direct connection with the unlawful use of force or other serious violations of international norms of jus cogens character. However, the Security Council has never taken this position with respect to Kosovo. Further, the Court reasoned that the exceptional character of those resolutions containing a condemnation of a declaration of independence confirmed the absence of a general prohibition against unilateral declarations of independence under international law.
The Court further determined that the law applicable to the situation on 17 February 2008 was made up of Security Council resolution 1244 (1999) and the UNMIK (United Nations Mission in Kosovo) regulations promulgating the Constitutional Framework for Provisional Self-Government defining the responsibilities relating to the administration of Kosovo.
To determine whether the declaration of independence constituted a violation of these laws, the Court first addressed the question of the identity of the authors of the declarations. The Court found that the authors should be regarded as representatives of the people of Kosovo, acting outside the framework for the interim administration. In accordance with the Court’s reasoning this further means that due to the fact that there is no specific request addressed to the representatives of the Kosovo Albanians to comply with certain aspects of Security Council resolution 1244, they cannot be considered as legally prohibited from issuing a declaration of independence.
Further, based on the arguments that the authors of the declaration of independence were not part of the Provisional Institutions of Self-Government and the fact that the declaration could not be regarded as an act intended to ‘take effect (..) within the legal order in which the Provisional Institutions operated’, the ICJ held that the declaration cannot be seen as violating the Constitutional Framework established under UNMIK.
The Court thus concluded by ten votes to four “that the adoption of the declaration of independence of 17 February 2008 did not violate general international law, Security Council resolution 1244 (1999) or the Constitutional Framework [adopted on behalf of UNMIK by the Special Representative of the Secretary-General]”, and that “[c]onsequently the adoption of that declaration did not violate any applicable rule of international law”.
So basically to fly at UN/ICJ, the unilateral declaration needs their prior (tacit) nod, at least in the form a provisional government framework (essentially a provisional constitution) approved by the UN, effectively removing the territory from the rulings of its former owner-state constitution. Furthermore, that provisional constitution must at the very least not prohibit the unilateral declaration. And that didn't happen in the case of Catalonia, so Spain's constitution (which has such prohibitions) still applied. So, no, it wasn't illegal for Spain to declare the Catalonia referendum illegal, at least not under the interpretation that ICJ gives to such matters.
And as a footnote, at least two answers and one comment here have claimed that the definition of "people" is too vague to clearly cover Catalonia. I think the analogy with Kosovo is obvious, and the test that ICJ devised in that case again relevant (quoting the Wikipedia summary):
Criteria for the definition of "people having the right of self-determination" was proposed during 2010 Kosovo case decision of the International Court of Justice: 1. traditions and culture 2. ethnicity 3. historical ties and heritage 4. language 5. religion 6. sense of identity or kinship 7. the will to constitute a people 8. common suffering.
I don't see how Catalonia would fail this test. The actual problem is that nothing (the UN did) overrode the Spanish constitution's prohibition on [unilateral] secession, unlike in the case of Kosovo.