That's pretty much* the truth for all the progress bars. For example, if the badge requires 200 defeats of a given type of boss, every two defeats will increment the bar one tick.
Since Immortal requires 1,000,000,000 damage taken, each tick should be 10,000,000 damage.
* I say "pretty much" because I haven't seen an exception to the rule. There might be one somewhere that I haven't been exposed to.