The COVID-19 pandemic has huge effects on the global community and an extreme burden on health systems. There are more than 185 million confirmed cases and 4 million deaths as of July 2021. Besides, the exponential rise in COVID-19 cases requires a quick prediction of the patients' severity for better treatment. In this study, we propose a Multi-threaded Genetic feature selection algorithm combined with Extreme Learning Machines (MG-ELM) to predict the severity level of the COVID-19 patients. We conduct a set of experiments on a recently published real-world dataset. We reprocess the dataset via feature construction to improve the learning performance of the algorithm. Upon comprehensive experiments, we report the most impactful features and symptoms for predicting the patients' severity level. Moreover, we investigate the effects of multi-threaded implementation with statistical analysis. In order to verify the efficiency of MG-ELM, we compare our results with traditional and state-of-the-art techniques. The proposed algorithm outperforms other algorithms in terms of prediction accuracy.