Another thing to look at would be filtering those results.  Is a report with 100K to 500K rows actually useful in any manner?  I am not asking if the data is useful, but is a REPORT with that much data useful?  
From an end user side of things, looking at 100,000 rows of data would make my end users eyes bleed.  Most of the reports on my SSRS server return as few rows as possible.  We try to direct the results to the specific users using filters.  So end users only get rows that are of interest to them.  If we sent them reports with 100,000 rows (or even worse; 500,000 rows), most of them would be ignored.
Also, how wide are the rows?  The more data you pull back, the slower the report will be.  
If I am not mistaken, SSRS puts all of the data for the report (after applying filters) in memory and then it will break it out into pages.  So the larger the data set, the slower this process will be.  Especially if you end up having memory pressure on your SSRS server.  Do you have enough RAM to handle the 100k-500k rows of data?  If not, it will be dumping that to disk which will make this even slower.

If the end goal is to export this to some format, you may get better performance using a different tool for this.  One example I can think of would be SSIS or even Excel.  With excel, the end users could just pull the data as they need it.  It's still be slow trying to pull in that much data, but then they only need to click on the "refresh data" button whenever they need fresh data.

Or, depending on how the end user is consuming and using the data, building an application in C# that would display the in a datagridview or similar format might be a better option.