I understand that the atmospheric temperature is sensed relative to external body temperature. However, is the sensation of warmth registered linearly, or is it on a logarithmic scale, similar to sound that works on the Decibel scale? Or is it on another scale entirely?
The human sensation of warmth is not the measurement of static temperature. Humans detect the rate at which heat is leaving (or entering) their body. For instance, if you are sitting in your 0 degree car in the morning, your hand in the open air will feels warmer than your hand touching the steering wheel, despite them both being at 0 degrees.
The reason is that heat conduction from your hand to the steering wheel is much faster than convective heat transfer from the air. So you feel "colder" touching the steering wheel, but it's really that you're losing heat faster.
Scholarpedia's article on temperature receptors: http://www.scholarpedia.org/article/Thermal_touch#Temperature_receptors
...Cold receptors respond to decreases in skin temperature over a range of 5-43 °C...
...In contrast, warm receptors signal that skin temperature has increased...
A more general answer/comment is that technically almost nothing in biology is really linear.
In a linear relation, when one variable increases the other increases proportionally. In biological systems this typically cannot happen because of physical limits (such as the number of molecules), which tend to produce saturation at some level.
For example, when a substance is "sensed" by the receptors of a cell, sensing would become saturated as the receptors approach maximal capacity. In a similar manner, heat sensing will be limited by a maximal capacity and saturation of the nervous system. This is of course not specific to sensing but is a general characteristic of biological systems, because they are ultimately made of a finite number of components.
That said, sometimes a linear-like relation is observed at a specific range of values. For example, this is a mathematical characteristic of a class of functions called logistic functions. At ranges that are far from saturation, these functions have approximately linear behavior.
In the following example figure I marked (black box) the "linear-like" regime of a simple logistic function y=1/(1+100*exp(-x)):