Could you bring the check with coffee? We're running late.
This does not imply that the person speaking and the person/people with him are late for some event. However, the speaking person believes that under the expected conditions (traffic, speed limit, distance to travel, etc) that the speaker and those with him will possibly be late for the event.
I'm running late.
Yes, this could mean "I expected to leave to go to the movie five minutes ago, but if I drive fast, I think I will be there on time."
We're running out of time.
Used for some dramatic event with a clear deadline such as a time bomb getting ready to explode or a timed test at school.
We're running short on time.
This idiomatic expression uses on, instead of of.
This phrase is used for less dramatic events or for events where there is more time remaining, than the previous phrase. For example, if the time bomb had just reached the one minute mark, this would be fine. If the time bomb was near fifteen seconds, I would use "out of time."
We're running 10 minutes over.
This is correct, but may not mean what you intend. Suppose you were in a meeting that was scheduled from 2:00 to 3:00. If it is 3:10 and the meeting is not over (ended), then this phrase would be good.
"It's 10 minutes overtime. or We're 10 minutes overtime."?
Overtime as a single word, means something different.
So, "It's 10 minutes overtime," might be the answer to "Hey John, how far is the game into the fourth quarter?" (basketball).
It could also answer the question "Hey James, you are only scheduled to work until 6:00, what are you still doing here?" (employment).