I had a similar situation to this although my total record count was 68K rows. In my particular situation I was working with Client Data so was able to circumvent this problem by setting up a 'Tab' type system so that the grid loaded clients whose last name began with A, B, C, D etc based upon which tab was clicked.
What I might first suggest is see if it is the amount of data you are trying to bring forward or if you have some other on page elements working against you. So execute a query that will only return you, say, 50 rows of data from your entire result set. If this speeds things up you are simply loading to much data into the grid for it to be effecient.
If this does not speed things up you have something else that is slowing you down.
Read this if you want to know how to get a correct reply for your question:
Technical Editor for:
Professional Search Engine Optimization with ASP.NET
Professional IIS 7 and ASP.NET Integrated Programming