you should show full mysql query, db structure and description of records then, we can try to help you...
If your are using MySql/InnoDB, since it has the ACID properties it has to check the table rows visible within its own transaction to find the answer, otherwise you would loose the ACID properties. The same goes for Postgresql. MySql /MyISAM uses a shortcut using a single field in a table to mark the number of rows in the table, which is a single lookup which is faster. Now you can guess why some people say MyIsam is faster. It is faster for this specific operation that is used on websites, since it does not give you ACID properties.
If the Recordset.RecordCount works like the recordsets I know then then the recordset is a client side list with entries which are the result of your query. And gues where the resultset comes from, yep the DB server. So instead of a simple query in to the DB server your are doing a select all records, then transferring them and then asking client side how many there are. Sorry this sucks in terms of memory and bandwidth. and does not solve the question of why the count is so slow. Again I ask the very SIMPLE question what table type are you using deriklogoc myisam or innodb or an other ?