No matter how you do it, evaluating a polynomial at 10,000,000 different points is going to take a long time. I would suggest trying at smaller data sizes first to get an estimate of how long you think it might take in order to see if it is a reasonable approach. You may find it necessary to reduce the size of your data or use random data with a similar distribution.
If you have the Parallel Computing Toolbox you may be able to speed up the computation by performing it in parallel.
