If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (since it's a product of two sizes)? Or something else?
I feel calling it "linear" is confusing because O(m + n) is also linear but much faster, but I feel like calling it "quadratic" is also weird because it's linear in each variable separately.
In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.
To elucidate on the discussion in the comments, it matters what you're measuring growth relative to.
As mentioned by @Kaveh, $O(mn)$ is not linear in both at the same time, but is linear if one is a constant and the other one grows.
On the other hand, $O(m+n)$ would likely be considered linear. Intuitively, if $m$ doubles, or if $n$ doubles, or even if both $m$ and $n$ double, $m+n$ cannot more than double. This is not true of $mn$; if $m$ and $n$ both double $mn$ goes up by 4. This is why in many contexts this running time would be considered quadratic. I give an example of this with string matching in a couple paragraphs.
But usually when you're using Big-$O$ notation, you're using it in reference to something in particular. Since we're mostly theorists, it's generally the size of the input to the problem.
Let's take Matrix Addition, for example. Adding two $m\times n$ matrices takes $O(mn)$ time. But each element of our input is only touched once, so this would usually be called linear. Put in other words, our input is of size $O(mn)$, so a running time of $O(mn)$ is linear in the size of the input.
Now let's look at string matching--namely, we are given a string of size $m$ and a string of size $n$ and we want to see if there is an occurrence of the smaller string within the bigger string. We can check this naively in $O(mn)$ time; this would generally be considered quadratic. Why? If $m$ and $n$ can be anything, set $m = n$. Then our running time is $O(m^2)$ and our input is of size $2m$.
On the other hand, if we use the Rabin-Karp algorithm, we get (on average) $O(m+n)$ time. Our input consisted of both strings, so our input was of size $O(m+n)$ as well. Therefore, this would generally be referred to as linear.
To sum up: $O(mn)$ is generally called linear for things like matrix multiplication because it's linear in the size of the input, but it's generally called quadratic for things like string matching because of the smaller input. Which term is appropriate depends on the context you're using it in.
If you are measuring the running time in $(m,n)$ then $O(mn)$ is not a linear function in $(m,n)$. If there is no relation between $m$ and $n$ this function can grow quadraticly in general.
However it is a linear function in each of them separately, i.e. if you fix one of them and look at the growth in the other variable then it is a linear function in other one.
To measure the complexity of the problems with multiple inputs, one way is to find the dominant variable and then bound other inputs based on that variable. With this approach you could have the complexity function based on single variable.
Given some Language $L = \{w_1\#w_2|w_i \in (\Sigma\setminus\{\#\})^*,\dots\}$ and a function $f$ such that $\min\{|w_1|,|w_2|\} \leq f(|w|)$ for every $w=w_1\#w_2 \in L$ you can estimate the running time of an $\mathcal O(|w_1|\cdot|w_2|)$ algorithm which recognizes $L$ as $\mathcal O(f(|w|)\cdot(|w|-f(|w|))= \mathcal O(f(|w|)|w|-f(|w|)^2)= \mathcal O(f(|w|)|w|)$.
This means you get linear time, if the smaller part of your input is constant (relative to the whole input), something in between (like $\mathcal O(n\log n)$) if it's sublinear and quadratic runtime if it's linear.
