> A: Did you see any birds at the park?
> B: Yeah, no - I didn't see any.
B is first acknowledging the question and it's intent - as well implying that maybe he did look for birds - which then flows into the fact that 'no' - he did not see any.
This can be done with the 'No, totally' example as well.
> A: I wasn't sure if you'd like to go to the park - do you want to?
> B: No, totally! Definitely want to go.
B is first saying 'No' to the implied "You don't want to go.". B is essentially saying 'The assumption you made was wrong - I do indeed want to go'.
Granted, I made these examples to be easy to dissect, and it's likely that from this pattern, it devolved into common vernacular despite being used in this way. But I think it still holds up for most uses.