It's even better in Russian: доверяй, но проверяй, doveryay no proveryay

It's better because it displays both words are semantically related. In fact, "verify" is cognate with their root, vera/veryat', probably a common Indoeuropean root but I'm too lazy to verify (pun intended).