O Time Machine faz o backup somente de partições HFS +, portanto, você precisará usar o Apple Disk Utility para formatar a partição do Time Machine.
Para Linux, você pode usar qualquer sistema de arquivos para o qual seu SO possa gravar, mas eu pessoalmente uso ext3 ou ext4. Você pode formatar isso usando o GParted, lembre-se de tocar apenas na partição Linux.