Think I have come out with the proper solution:
on template::list::prepare, I save an entry for "count_query" in the list properties, then pass it to template::paginator::create together with "page_query_substed" as before.
Here, I check for a cache entry for the full_row_count, as happens for paginated row_ids. As happened before, if row_ids are not in the cache, I call paginator query into template::paginator::init. Into this proc I have added also the call to the count_query and the saving of the value in the cache.
This way now paginator has a new property called "full_row_count", which can be retrieved from template::paginator::get_full_row_count.
To have a common interface for getting the count in template::list, I have created a proc called template::list::get_rowcount. On a paginated list, it calls template::paginator::get_full_row_count, otherwise it just returns the size of the undelying multirow.
Its easier done than explained... Anyway, checks on both paginated and not paginated lists on my instance work. Is it ok if I commit the change?
Antonio