ブラジルは現在18カ国と条約を締結しているそうですが、憲法に前述のような記載がある以上、
実効性については疑問がありますね。何か理由や抜け道があるのかも知れません。
諸外国間の犯罪人引渡しについては見当も付かないので、googleで検索してみるとこんなものが。
国際的な組織犯罪の防止に関する国際連合条約(Wikipedia)
まだ斜め読みしかしていないのですが署名国は147、締約国は110となっています。
ただ「三人以上の者から成る組織された集団」や「重大な犯罪」が主な対象で、具体的には
人身売買や資金洗浄など、性質上必然的に国をまたぐ犯罪を取り締まる国際条約のようですから
単に「外国で犯罪をおこない、国外に逃亡した者」については対象外の可能性が高いですね。
おそらく、この条約の他にもっとピタリと該当するようなものがあるのでしょう。
何ていうか、まだまだ知らないことがたくさんあるんだなあ(当然ですが)。