A vector of $10^6$ elements is not a particularly large sample for density estimation. Linear binning can be used to accelerate kernel density estimation (similar to usual binning, but probability mass is linearly distributed from data points to surrounding grid points), as well as FFT or even splines (which are very fast to evaluate, once the coefficients have been computed). There is a very nice [pre-print][1] on the topic by Henry Deng and Hadley Wickham. If you are only interested in kernel density approaches, and not in stuff such as shifted histograms or penalized likelihood, then the tricks mentioned before are implemented in some R packages, such as `KernSmooth`, `sm` and `density` (this last one is included in base R). Personally, I found also `ASH` and `logspline`
 to work well (and be fast), but they're not based on the KDE paradigm, which may or may not be what you're looking for. 

Also, another thing that sometimes makes a difference (for example, it speeds up the FFT step, which however is rarely the limiting step in terms of performance), is to use an R binary which is optimized to take full advantage of the BLAS and LAPACK for the specific machine you're working on, as well as run on multiple cores if your PC has a multicore CPU (which I think is true for all PCs on the market today). For this, If you have a Windows pc, I definitely recommend using Microsoft R Open. If you have a Mac, then compiling R with the Accelerate framework should do the trick. I don't know how to get architecture-optimized BLAS & LAPACK under Linux, but I'm sure there's a way.  

  [1]: http://vita.had.co.nz/papers/density-estimation.pdf