Algorithmic run time is "time complexity." There are many different types of complexity which we can measure in some sense, including space complexity, energy complexity, circuit complexity, and architectural complexity.

http://en.wikipedia.org/wiki/Computational_complexity_theory

I agree with you that there seems to be no foolproof way to measure the overall "software complexity" of a piece of software. There are a lot of methods proposed, but none is provably optimal or even all that useful it seems. Search "Evaluating Software Complexity Measures" by Elaine Weyuker for a somewhat dated paper discussing the topic. I would be very interested if anyone had any recommended resources on the current state-of-the-art regarding software complexity measures.

Seems to me the only way to measure complexity absolutely would be some sort of extension of the minimum description length principle -- what is the shortest way we could write the specification for the entire machine + software that runs on it. Of course this seems completely infeasible for any real world task.