What is the reason that is FFT multiplication slower than other methods for small N?
The Wikipedia FFT article says that the split-radix FFT algorithm requires $4N\log_2N-6N+8$ real multiplications and additions.  Multiplying 2 degree $M$ polynomials results in a polynomial of degree $2M$, so the "FFT multiplication of two polynomials" goes like this:

FFT (size 2M) of polynomial f(x) (evaluate f(x) at the 2M primitive roots of unity)
FFT (size 2M) of polynomial g(x) (evaluate g(x) at the 2M primitive roots of unity)
multiply each of the 2M fourier coefficients together
inverse FFT (size 2M) of the fourier coefficients to get the resulting polynomial


Perhaps there is a way to make the first two FFTs faster based on the fact that the $M+1$th through $2M$th coefficients of f(x) and g(x) are all zeros, but I don't know it offhand.

So we are doing 3 FFTs of size $2M$ plus an additional $2M$ complex multiplies (each of which is 4 real multiplies and 2 real additions so:
$$3 (4(2M)\lg2M - 6(2M)+8)+4M = 24M\lg M -8M+24$$
additions and $24M\lg M - 4M + 24$ multiplications.

Meanwhile the naive polynomial multiplication algorithm (convolution) takes $M^2$ real multiplications and $(M-1)^2$ real additions.  (Proof left as exercise for the reader.)

Thus the naive algorithm will be faster for $M \leq 128$, while the FFT based algorithm will probably be faster at $M \geq 256$, and the crossover will be somewhere between 128 and 256.  (Proof left as exercise for the reader.)

I did this quickly and sloppily, so I'm probably off somewhere (e.g., the forward FFTs are real -> complex, (but is there a DCT version that would be cheaper?) while the reverse is complex -> real (which may have slightly different constants than the ones I used,) and I only did the evaluation at $M$ power of 2 (FFT of non-power of 2s is more expensive.))  Nonetheless, the point stands: the constant multiplier for the FFT is approximately 24, while the constant multiplier for the naive convolution is 1, so you need to compare (something like) $24M\lg M$ to $M^2$.