I was browsing through this page when I noticed that Malay ‘sa’ is a borrowing from Sanskrit. Sanskrit examples are here. Googling for this ‘sa’ prefix, there seems to be no such common affix in Malay, as enumerated here, although there is a se-, this originated from the word for one, as explained there.
Malay ‘sa’ is a prefix meaning “with”, and in Sanskrit means “with; along with; accompanied by”. Although the affix means “with”, its possible that this has shifted in meaning to be used as an oblique marker instead. There are lots of borrowings that shifted in meanings. Also, it is not uncommon for Philippine languages to borrow prepositions or markers, like Spanish pero, o, ni.