Does your graph actually have to be in Excel? With that many data points the performance would be horrible.
One suggestion might be to use a third party component to generate the graph. The specific technique for how to accomplish this depends on whether you have to be able to view the data in excel or whether the output graph simply needs to be available elsewhere.
If the graph does not need to be visible within Excel, then just pass the data points and view the image in the graphing application or a web browser.
If you do need to view the graph with excel, you could make a call to the external graphing application and pass it a collection of data points. When it returns the image just insert it in excel with vba.
I can give you more info on both approaches if you need.
Also, other considerations might include whether you need to have drill down capability on the graph. With this many data points, I can not imagine that you would.
If you can answer the following questions, it might help folks formulate better answers.
What sort of user interface will be presenting the output of these items? (e.g. Excel, ASP.NET Web Application, Windows Forms, WPF, Silverlight, other.)
Are these graphs supposed to be generated in real time at a user's request or are they generated and stored? If they are generated on demand, what is the maximum amount of time your users would consider acceptable to wait?
How important is it that you actually use Excel? Are you using it because it is a requirement for display, or is that just what is handy?
How important is the "Wow factor" for the display of the graphs? Is simply having the graphs, or do they have to be extremely beautiful?
Do users require any ability to drill down into the graph, or is simply being able to view the image sufficient?