Assumindo-se que não existe nenhuma "hierarquia" entre os prefixos (ex.: toda palavra que começa com `ro` *também* começa com `r`), uma maneira simples e direta é usando o [`itertools.product`][1]. Ele vai combinar cada elemento da primeira lista com cada elemento da segunda lista. Então basta filtrar aqueles que o segundo é prefixo do primeiro, e contar:

    >>> import itertools
    >>> palavras = ['rato', 'roeu', 'rolha', 'rainha', 'rei', 'russia']
    >>> prefixos = ['ro', 'ra', 'r']
    >>> len([palavra for palavra,prefixo in itertools.product(palavras, prefixos) if palavra.startswith(prefixo)])
    10

Note que as 4 primeiras palavras foram contadas duas vezes (pois elas começam tanto com `ro`/`ra` quanto com `r`). Para uma solução que só conte cada palavra uma única vez, veja por exemplo as respostas do [Orion][2] e [Anthony Accioly][3] (a do [Dherik][4] faz ambos, e ainda conta as ocorrências por prefixo).


  [1]: https://docs.python.org/3/library/itertools.html#itertools.product
  [2]: https://pt.stackoverflow.com/a/57381/215
  [3]: https://pt.stackoverflow.com/a/57384/215
  [4]: https://pt.stackoverflow.com/a/57373/215