Accurate cell classification is the groundwork for downstream analysis of single-cell sequencing data, yet how to identify true marker genes for different cell types still remains a big challenge. Here, we report COSine similarity-based marker Gene identification (COSG) as a cosine similarity-based method for more accurate and scalable marker gene identification. COSG is applicable to single-cell RNA sequencing data, single-cell ATAC sequencing data and spatially resolved transcriptome data. COSG is fast and scalable for ultra-large datasets of million-scale cells. Application on both simulated and real experimental datasets showed that the marker genes or genomic regions identified by COSG have greater cell-type specificity, demonstrating the superior performance of COSG in terms of both accuracy and efficiency as compared with other available methods.