How can I be really sure that our MySql database scales for millions
of users for given query? Is there any way to estimate how long, say,
10 000 simultaneous queries take, based on how long one individual
query takes (database filled with large amounts "junk data" to
simulate data of millions of users)? What kind of stress tests should
be performed in addition?

Well, for one i doubt there will be more than 10,000 queries used in
any one time. However if your project will be expecting usage like
that, then i hope you have some serious processing power and hardware
behind this. If you install PHPMyAdmin (a web interface which allows
control over your SQL databases), then you can test your database by
inputting a query:

1) click on query window hyperlink - this should popup a window
2) within this popup, enter your SQL syntax (query) and press Go
3) this shall then return with your request and also state how long
the query took to process

Now you know how long your query takes to process, simply multiply
this by the number of simulataneous users (e.g. 10,000). This is only
an estimation, the only true way to find out would be to get 10,000
users to execute the query.

You may find the answer yourself on mysql.com. They provide a
benchmarking app at http://www.mysql.com/why-mysql/benchmarks/ which
includes the demo code.
I've not run it myself but i'm presuming it comes with everything the
whitepaper associated with it describes.