Adding where condition with index make query slower(use filesort and temporary)
this index actually helped: deleted_at, category_id, however, I tried to do this without adding new index
Since there are much more records where deleted_at is null, i tried next queries:

SELECT 
    COUNT(*) AS count_all,
    `users`.`category_id` AS users_category_id
FROM
    `users`
WHERE
     `users`.`id` NOT IN (SELECT `users`.`id` FROM `users` WHERE `users`.`deleted_at` IS NOT NULL)
GROUP BY `users`.`category_id`;


And query optimizer used much better schema. I will try it soon on big set and hoe it will work.