What is the cost of encrypting of long message with public-key cryptography? Let m be a message of arbitrary size, potentially very large.
Is it necessary to use larger parameters in the public-key encryption scheme in order for the receiver to decrypt that message?

My guess is that, in the case of RSA, the size of the message cannot exceed the size of the modulus. I assume this holds for any public-key encryption scheme.

If so, what kind of algorithmic complexity are we talking about: is it linear in the input size (the message), or worse? [I assume it's worse]

EDIT: I don't want to use symmetric-key cryptography.

EDIT 2: You can assume that we possess a secure channel over which we'll send the encrypted message.
The real problem is not the encryption or even the decryption of an encryption scheme with huge values, it is the generation of the key:

For RSA, ElGamal, Paillier, etc. you need one or more large primes, which make up a modulus for your computations. In practice, you can find large primes by using the Miller-Rabin primality test. It has a run time of $O(t \log^3 n)$, and for large numbers it can be improved to $O(t \log^2 n)$ if using FFT-based multiplication. $t$ notes the number of test runs and you have an error rate of $1/4^k$, where the test says prime for a coposite number. While the runtime with multiplication optimazation has the smaller exponent, the Big-O notation does hide constant factors, and I don't know where the break-even is, but let's just assume the current crypto libraries already use the optimzation.

As a reference in this SO answer generating a $2048$ bit RSA key (which is generating two $1024$ bit primes and a tiny amount of its computation time to find $e$ coprime to $\phi(n)$ and calculating $d$) takes around $1$ sec. So $\approx 0.5s$ for a $1024$ bit prime.

If we want to increase the size by a factor $a$, then the Miller-Rabin test takes $a^2$ times longer. However, we also need to test $a$ times as many numbers on average to find an actual prime number. Example: A random $1000$ bit number is prime roughly with probability $1/ln(2^{1000}) = (\log 2)/ 1000$ and we need on average $1000/(\ln 2)$ tests to find a prime, a random $2000$ bit number is prime with probability $(\log 2)/2000$, and on average we need to test $2000/(\ln 2)$ numbers to find a prime. This means, we expect to run the algorithm on $a$ times as many numbers to find a prime.

For example, for a prime with $1 M$ bits for example and an estimate of $0.5$ sec for a $1024$ bit prime, we have a factor of $~976.5$ in size, so the runtime for Miller-Rabin itself is $0.5 \cdot 976.5^2$, and we need to test $976.5$ as many values, resulting in an overall runtime of $\approx 465 M$ seconds, which is around $14.76$ years.

In case you want to use RSA you need two of these primes, so after 30 years you have a RSA modulus with $2,000,000$ bit, which allows you to encrypt $0.25$ MByte of data in one piece. Of course using a large computing center will speed this up, but the real problem is the size, since I guess you didn't have $0.25$ MB of data in mind when you wrote "potentially very large".

Edit:
The encryption and decryption scale much less from the size increase. For RSA, you can still use a small exponent in the encryption, this doesn't have to be much larger than current ones. That means the number of steps in square-and-multiply are roughly the same, just each multiplication and modulo operation takes more time. Decryption then involves a number of length of the modulus, but overall it is still quadratic at worst, and much less than prime generation.