First we would like to know if it is induction motor (ceiling fans) , universal motor (table fan) or some other kind.
If its induction motor varying the frequency will be used (difficult)
If it is universal motor you can control it by using ac chopping circuit using arduino(easy).