I don't get the word's relationship to cremation, either.
The Romans used to keep pigeons in holes cut into walls.
Since medieval Italians did not burn their dead, and since they still kept pigeons this way, they thought that the ancient Roman cineraria (ash-holes, cinder receptacles) dotting the landscape were columbaria because it did not occur to them that ashes of people would be kept in such structures.
So they called all such structures columbaria and the term stuck.
A lot of ancient Roman cineraria did become actual columbaria used by Italian pigeon farmers. I saw an Etruscan one in Orvieto.