Why is XML called a “language” exactly?

Because it is a language. A markup language, not a programming language.

Notice that natural human languages like English and Spanish don't "do" anything either. In fact, technically C++ and Java and the like don't "do" anything until they're fed into a compiler and the output gets executed. Doing stuff and being a language are largely orthogonal to each other.

Let Σ be a non-empty, finite set of symbols, called an alphabet. Then Σ* is the countable infinite set of finite words that can be formed by concatenating zero or more symbols from Σ. Any well-defined subset L ⊆ Σ* is a language.

Let's apply this to XML. Its alphabet is the Unicode character set U, which is non-empty and finite. Not every concatenation of zero or more Unicode characters is a well-formed XML document, for example, the string

<tag> soup &; not <//good>

is clearly not. The subset XML ⊂ U* that forms well-formed XML documents is decidable (or “recursive”). There exists a machine (algorithm or computer program) that takes as input any word w ∈ U* and after a finite amount of time, outputs either 1 if w ∈ XML and 0 otherwise. Such an algorithm is a sub-routine of any XML processing software. Not all languages are decidable. For example, the set of valid C programs that terminate in a finite amount of time, is not (this is known as the halting problem). When one designs a new language, an important decision to make is whether it should be as powerful as possible or whether the expressiveness would better be restricted in favor of decidability.

Schemata are an addition to XML that allow refining the set of well-formed documents. A well-formed document that follows a certain schema is called valid according to that schema. For example, the string

<?xml version="1.0" encoding="utf-8" ?>
<root>all evil</root>

is a well-formed XML document but not a valid XHTML document. There exists schemata for XHTML, SVG, XSLT and what not else. Schema validation can also be done by an algorithm that is guaranteed to halt after finite amount of steps for every input. Such a program is called a validator or a validating parser.

Because you can define your own schemata, XML is called an extensible language, which is the origin of the “X” in “XML”.

You can define a set of rules that gives XML documents an interpretation as descriptions of computer programs. XSLT, mentioned earlier, is an example of such a programming language built with XML. More generally, you can serialize the abstract syntax tree of almost any programming language quite naturally into XML, if this is what you want.

In computer science, formal language is just a set of strings, usually infinite and often described using rules (two common versions of those rules are regular expressions and formal grammars).

Note that this means that all a language needs is syntax, language doesn't need to describe what each valid string means (that's called semantics).

Now, this means that programming languages are formal languages that also have semantics, which describes some computation. And for example XHTML is a formal language, whose semantics describe (roughly and informally) how a hypertext document looks and behaves.

XML is still a language, even though it doesn't have semantics itself (but many languages derived from XML do, like XHTML and XAML).

Technically, binary formats are also languages, but they're not called that way. The term "language" is reserved for human-readable formats.

A language is a method of conveying information.

A programming language is a method of conveying algorithms.

A markup language like XML is a language for conveying data.

XML is a meta-language. You use it to define specific languages. Languages never do anything, they just allow us to express things. Also, it is not true that XML is a "storage language". Just the opposite, in fact. You can store XML docs however you please. XML is better thought of as a transfer language. PS. If you don't think XML "does" anything, you'll have to explain how it is that many systems (e.g. jetty) use XML as a (bad) programming language. It's a lamentable abuse of XML, but it exists in the wild, and that just one of many examples.