We present Panmap, a tool that uses phylogeny-informed structure to map, align, and genotype sequencing reads against mutation-annotated pangenomes containing millions of genomes. Its phylogenetically compressed k-mer index records only the sequence changes occurring along evolutionary branches, allowing reads to be efficiently compared with both observed genomes and reconstructed ancestors. Compared with existing methods, Panmap reduces index size by as much as 600-fold and shortens construction time by more than three orders of magnitude. It can place a SARS-CoV-2 sample at 100× coverage among 20,000 genomes in 0.4 seconds and among 8 million genomes in less than two minutes. Panmap also accurately identifies haplotypes and estimates their abundance in metagenomic samples, while sensitively placing ancient environmental DNA without requiring prior alignment. Overall, the method makes very large pangenomes practical for read mapping, genome assembly, alignment-free phylogenetic placement, and metagenomic analysis.