Existem, na data que estou escrevendo esta resposta, 1383 métodos Parse() e 266 TryParse() apenas no código fonte do .NET disponibilizado pela Microsoft (Veja também no GitHub). Claro que isto inclui todos os overloads.

Parse de inteiros

Imagino que sejam dos métodos usados para converter uma string que provavelmente contém dígitos numéricos em valores numéricos de um determinado tipo. Embora existam implementações diferentes, elas são parecidas e vou me concentrar no int.Parse e o int.TryParse.

Formas de usar:

int value;
try {
    value = int.Parse("!123x6");
} catch(FormatException) {
    value = -1; //solução horrível mas serve para o exemplo
}

int value;
if (!int.TryParse("!123x6", out value)) {
    value = -1; //solução horrível mas serve para o exemplo
}

A segunda forma me parece mais limpa. E em C# 7 ainda pode ser mais curto:

if (!int.TryParse("!123x6", out var value)) {
    value = -1;
}

Coloquei no GitHub para referência futura.

Performance

Já lhe mostraram os comparativos de tempo. Mas isso não é tão importante. Lembre-se que otimização prematura não deve ser feita. Só se preocupe se existirem métricas que indiquem que um destes métodos está causando uma lentidão prejudicial. Mas por coincidência o mais rápido é o mais indicado, semanticamente falando.

Exceção X dado inválido

Você usa um destes métodos para converter um texto em número, se e somente se existir um número válido identificável pela rotina de parse. Se não for possível converter, isto é um dado inválido? Ou é uma exceção na execução do programa?

A resposta que você der vai determinar qual dos métodos usar. Tem que usar o que é semanticamente adequado antes de qualquer outro motivo, especialmente otimização.

Eu entendo e conheço diversos programadores experientes que entendem que na imensa maioria dos casos, o fato da conversão não ser possível indica a invalidade do texto analisado para o propósito requerido e uma invalidade de dado deve ser notificada ao programa de uma forma simples. Isto é uma informação que faz parte da "regra de negócio" e não do mecanismo de conversão. Na verdade eu não consigo ver um caso para usar o Parse que não esteja consertando o mecanismo errado. O TryParse() foi criado posteriormente porque foi identificado que o Parse() era o mecanismo errado.

Exceção degrada desempenho

A excelente resposta do SO mostra claramente que o desempenho do Parse() só consegue ser comparável, mas não melhor, se todos os dados analisados são válidos. Quanto mais dados inválidos no seu roll, pior fica o desempenho do Parse(). Até porque tratar exceções é um processo extremamente lento.

Você pode dizer que existem diversas exceções que podem ser lançadas durante o processo e você pode querer saber qual exceção é. Mas para que? O que você vai fazer com esta informação? Se o dado é inválido, você vai receber uma exceção FormatException. O que isto ajuda mais que um true ou false? Se for outra exceção, ela indica um erro de programação e não a invalidade do dado. Como você vai consertar um erro de programação? Um try-catch não resolve problemas de programação. Se alguém ainda acha que resolve, por favor, parem de fazer isto. Um problema de programação só deve ser manipulado antes de sair da aplicação, provavelmente fazendo um log e talvez melhorando a apresentação do erro para o usuário final, se o erro chegou em produção. Não dá para fazer mais nada!

Exceção não é fluxo normal

Ok, para tudo existe exceção (no sentido amplo da palavra, não o recurso técnico de programação), então pode existir um caso que dê para tratar, mas é raro. Geralmente quando acha um jeito de lidar com um erro de programação, provavelmente não deveria estar lidando com exceção (no sentido de Exception), deveria ter uma forma de interceptar isso pelo fluxo do programa. Tratamento de exceção não é fluxo normal. Tratamento de exceção deve ser feito com algo inesperado. Dado inválido é algo esperado, é algo que é normal acontecer e precisa ser tratado apropriadamente.

É preciso entender melhor como usar exceções. Trato deste assunto em outras respostas aqui e aqui e mais amplamente aqui (um bom lugar para começar navegar para várias outras respostas sobre o assunto).

Pra que usar o `Parse()`?

Eu não consigo me imaginar usando o Parse() para nada. Mas não terei problema em usar quando perceber que ele vai ajudar algum caso específico. Talvez um caso que precise resolver um corner case, um bug do .NET, sei lá, mas em condições normais, não há porque usá-lo.

Se quiser tentar entender melhor os métodos, leia seus fontes (tem que ir navegando pelas chamadas para ver todos os caminhos, mas o UI do site ajuda): Parse() e TryParse().

Como última nota, só não vá usar o TryParse() como nessa pergunta. O retorno não é tratado. Se um dado estiver errado, você tem um erro de lógica invisível em seu programa. Claro que eu não sei se há garantias que o TryParse() nunca vá dar dado inválido com o conjunto de dados tratado ali. Mas não confiaria em nenhuma garantia. Computadores falham, humanos falham mais ainda. Neste caso um Parse() teria sido melhor porque pelo menos daria um erro de programação e quebraria a aplicação. Não é o ideal mas é melhor que aceitar dados inválidos (bom, taí um caso para o Parse(), você tem certeza que nunca falhará).

Diferenças entre Parse() vs TryParse() no C#