Não consegui encontrar fonte que me esclarecesse a origem precisa das expressões em apreço. Todas elas decorrem de processos metafóricos, mas reconstruir o contexto factual da sua formação e difusão é tarefa por agora inexequível.

No entanto, em relação a «bater as botas» ou, na forma que encontro mais frequentemente em dicionários de expressões populares, «bater a bota», Afonso Praça, no Novo Dicionário do Calão, Lisboa, Casa das Letras, 2005, adianta alguma informação sobre a respectiva origem metafórica:

«Bater a bota — Morrer. [Também bater as colheres; bater a caçoleta; bater o tacão; esticar o pernil; ir para a companhia dos pés juntos; ir para a quinta das tabuletas.] [Explicação do coronel Aleu de Oliveira: "À semelhança de quando um militar na presença de um superior dá um passo à retaguarda e dá a seguir meia volta, quando se vai a retirar, batendo com as botas no chão, o ir-se embora desta vida é conhecido como o bater da bota."]

["(...) `E depois, vocês sabem como é: quando a gente tem as coisas até dá pena não se servir delas. De repente, sem pensar, olha, vai um tirinho, o tipo bate a bota, é homicídio, apanha-se uma talhada que nunca mais acaba´(...), Mário Zambujal, Crónica dos Bons Malandros.]

["(...) E então que trepa! Tinha a cabeça rachada de alto a fundo, e os ossos, em roda, tremiam como uma trémola. Puseram-lhe a extrema-unção e esteve a bater a bota (...)", Aquilino Ribeiro, Terras do Demo.]»

Sobre as outras duas expressões, encontro só registros que não abordam a sua génese metafórica em António Nogueira Santos, Novos Dicionários de Expressões Idiomáticas (Lisboa, Edições João Sá da Costa, 1988), em Orlando Neves, Dicionário de Expressões Correntes (Lisboa, Editorial Notícias, 2000) e no Dicionário da Língua Portuguesa Contemporânea, da Academia das Ciências de Lisboa:

Borra-botas

«borra-botas (pop): pessoa insignificante, desprezível. pobre diabo; Inês-da-horta; João-fernandes; João-ninguém; Zé-dos-anzóis; Zé-faz-formas; Zé-ninguém; Zé-prequeté; Zé-quitolas/quitólis; Zé-da-véstia» (Santos, op. cit.)

«borra-botas [bɔRɐˈbɔtɐʃ] s[ubstantivo] m[asculino] e f[eminino] s[in]g[ular] e pl[ural] 1. P[ouco] Us[ado] Mau engraxador de calçado. 2. Pessoa reles, desprezível. 3. Pessoa sem valor, insignificante. ≃ ZÉ-NINGUÉM. Aquele borra-botas pensava que podia passar à minha frente nas promoções da empresa.»

Suponho que a expressão remeta para a má apresentação de alguém que é tido em pouca conta por causa disso; o aspecto sujo e descuidado do calçado será o principal indício.

A mata-cavalos (a forma registada inclui a preposição a)

«a mata-cavalos (fam): diz-se do que é feito a ritmo muito acelerado, apressadamente, precipitadamente.» (Santos, op. cit.)

«A mata-cavalos — Com pressa; precipitadamente.» (Neves, op. cit.)

«Fazer qualquer coisa a mata-cavalos» parece, portanto, um uso hiperbólico, alusivo à época em que os transportes dependiam da tracção de cavalos, que podiam morrer de cansaço em situações de esforço extremo.