Categories have IDs (numbers), thus, items of any languages can be in the same category.
For example:
{LISTPAGES(categId="6",lang="en")}{LISTPAGES}
To change translate labels in tiki-browse_categories.php and tiki-admin_categories.php, just do as you would for Translating Interface