Found a solution shortly after. Will mention for convenience.
When you run mail_instance.list() you obtain a list of folders, such as:
(\Noselect \HasChildren) "/" "[Gmail]"
(\HasChildren \HasNoChildren \Trash) "/" "[Gmail]/Caixote do Lixo"
(\HasNoChildren \Flagged) "/" "[Gmail]/Com estrela"
(\HasChildren \HasNoChildren \Sent) "/" "[Gmail]/Correio enviado"
(\HasChildren \HasNoChildren \Important) "/" "[Gmail]/Importante"
(\HasChildren \HasNoChildren \Drafts) "/" "[Gmail]/Rascunhos"
(\HasNoChildren \Junk) "/" "[Gmail]/Spam"
(\HasChildren \HasNoChildren \All) "/" "[Gmail]/Todo o correio"
(these are in Portuguese)
The name of the "all mail" folder always contains the tag "\All" in the string, so just do a search for "\All" in all folder names that are returned by .list().
Then just extract the substring from the index of "[Gmail]" to the index of the first double quote after that, and you obtain the "all mail" folder name.