Depende muito do seu nicho.
Você pode, por exemplo, comprar relatórios especializados, se basear em relatórios públicos ou contratar uma empresa para realizar a pesquisa.
Imaginando um empreendedor solo com pouco capital, se basear em relatórios públicos pode ser a opção mais interessante.

Vejamos um exemplo:
Seu SaaS é um CRM para laboratórios de análise veterinária. Logo, seu público inicial são CNPJs de laboratórios veterinários.
Você pode buscar o CNAE dessa atividade e filtrar todos os CNPJs ativos e com mais de 2 anos de funcionamento, em tese esse é o tamanho do seu mercado.
Paralelo a isso, é importante ver a tendência do mercado, se está crescendo, estagnado ou encolhendo. Iniciar um SaaS em um setor em crise é uma das piores coisas que você pode fazer.

Dica: O exemplo não foi por acaso, o setor de pet care (clínicas, laboratórios, pet shops, plano de saúde...) é um dos que mais cresce no país ;)