O Coronel Aleu de Oliveira dá a seguinte explicação em Presença Militar na Língua Portuguesa (1993), também citada neste artigo do Ciberdúvidas:
À 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 a bota.
Eu nunca fui à tropa, mas encontrei a explicação daquilo a que o Coronel se refere neste blog do Tenente Perdigão. O militar para dar meia volta cerimonialmente, roda o pé direito na direção requerida e «o pé esquerdo vai assentar, com batimento, junto ao primeiro» (meu negrito em todas as citações). Podem ouvir e ver este batimento neste vídeo do exército brasileiro. Ao segundo 15 ouve-se o batimento dos pés esquerdos dos soldados ao voltarem à direita; ao segundo 35 vê-se e ouve-se o batimento do mesmo grupo ao fazer meia volta.
Agora a questão é como é que o Coronel Oliveira sabe que é esta a origem duma expressão que já vem do século XIX. No entanto a expressão é plausível por duas razões. Na meia volta militar é só o pé esquerdo que bate, e a expressão original parece ser bater a bota e não bater as botas. No Google Books só encontrei bater as botas a partir de 1962 (em A Rua e o Mundo de Fran Martins), enquanto bater a bota já aparece nas obras dos autores brasileiros Machado de Assis (1839-1908), Lima Barreto (1881-1922), Raul Pompeia (1863-95) e Artur Azevedo (1855-1908). O exemplo mais antigo que encontrei (dos que consegui datar) é de 1877 em A Pele do Lobo de Artur Azevedo:
Hei de ser promovido na primeira vaga que aparecer. O Cantidiano está por pouco a bater a bota. Verás se o lugar é ou não é meu!
Em Portugal a ocorrência mais antiga que encontrei é só de 1938, em Ocidente: Revista Portuguesa, o que sugere que a origem da expressão é brasileira.
A outra razão para a plausibilidade da origem da expressão na retirada do soldado da presença de um oficial, é que bater a bota também já foi usado, pelo menos no Pernambuco, simplesmente com o significado de ‘ir embora’, como atesta em 1935 a Revista do Instituto Arqueológico, Histórico e Geográfico Pernambucano:
Bater a bota; fugir, desaparecer, pôr-se ao fresco; morrer, “A rapazeada que folgava no bumba da Varzea deu tamanha vaia na Yáyá Prata, que envergonhada bateu a bota para o Recife”. ([revista] A Pimenta).
Encontrei uma explicação alternativa neste site, segundo a qual a expressão se teria divulgado durante a Guerra do Paraguai (1864-70) porque soldados feridos ao morrer «sacudiam espasmodicamente as pernas, batendo as botas uma na outra». Não são dadas quaisquer referências, e ficaríamos com cerca de uma década para de «batendo as botas uma na outra» se passar a «bater a bota» na obra de Artur Azevedo. Precisaríamos também de uma origem separada para o bater a bota no sentido pernambucano de ‘ir embora’.