Open Google on your phone. Go to System Settings > Google > Search. Uncheck the Show recent searches option.