Faits: A. Par jugement du 26 mai 2011, le Tribunal de première instance du canton de Genève (ci-après: Tribunal de première instance) a prononcé le divorce des époux A.X._, né en 1967, originaire de Genève, et B.X._, née en 1971, de nationalité autrichienne, après avoir débouté les parties de leurs requêtes tendant au prononcé de mesures provisoires (ch. 1), et a statué sur le sort de l'enfant (ch. 3 et 4). Le Tribunal de première instance a en outre notamment attribué à M. A.X._ la part de Mme B.X._ dans la PPE copropriété des parties, moyennant paiement par M. A.X._ d'une soulte de 696'486 fr. (ch. 12). La moitié de l'émolument de mise au rôle, soit 7'800 fr., a été mis à la charge de M. A.X._, les dépens étant compensés pour le surplus (ch. 15 et 16). B. B.a. M. A.X._ a fait appel de cette décision par acte déposé le 27 juin 2011, contestant notamment le montant de la soulte de 696'486 fr. due à son ex-épouse à titre d'indemnité pour l'attribution en sa faveur de la pleine propriété de l'immeuble (ch. 12) et la répartition de l'émolument de mise au rôle (ch. 15). Mme B.X._ a conclu au rejet de l'appel principal et formé un appel joint réclamant une soulte de 700'000 fr. et sollicitant de la Cour de justice du canton de Genève (ci-après: la Cour) qu'elle ordonne un avis aux débiteurs de son ex-époux. En relation avec la procédure d'appel, M. A.X._ s'est acquitté d'une avance de frais de 15'000 fr. et Mme B.X._ de 2'000 fr. B.b. Par arrêt du 11 mai 2012, la Cour a notamment annulé le chiffre 12 du jugement entrepris et condamné M. A.X._ à payer à son ex-épouse une indemnité de 700'000 fr. Les frais judiciaires d'appel fixés à 17'000 fr. et entièrement compensés par les avances de frais déjà opérées ont été mis à la charge de chacune des parties par moitié, de sorte que Mme B.X._ a été condamnée à verser 5'500 fr. à M. A.X._ au titre de remboursement des frais judiciaires avancés par ce dernier. La Cour a en outre dit que chaque partie supporterait ses propres dépens. C. C.a. Statuant le 18 juin 2012 sur le recours en matière civile formé par M. A.X._ contre cette décision, le Tribunal de céans l'a admis partiellement et a réformé l'arrêt entrepris en ce sens que l'indemnité due par M. A.X._ à Mme B.X._ a été réduite à 227'108 fr. La cause a en outre été renvoyée à la Cour pour nouvelle décision sur les frais et dépens de la procédure cantonale. C.b. Statuant par arrêt du 22 février 2013, après renvoi de la cause, la Cour de justice a confirmé les chiffres 15 et 16 du jugement du Tribunal de première instance du 26 mai 2011 constatant qu'ils n'étaient plus litigieux et fixé les frais judiciaires de la procédure d'appel de la même manière que dans l'arrêt entrepris du 11 mai 2012 (cf. supra B.b). D. Par acte du 11 avril 2013, M. A.X._ exerce un recours en matière civile au Tribunal fédéral contre cet arrêt. Il conclut principalement à son annulation et à sa réforme en ce sens qu'il soit dit que les frais judiciaires cantonaux, réduits à 5'515 fr. 50, soient répartis à raison de 1'378 fr. 90 sous déduction des 15'000 fr. déjà versés à sa charge et 4'136 fr. 65 sous déduction des 2'000 fr. déjà versés à la charge de Mme B.X._, de sorte qu'un montant de 13'621 fr. 10 devrait lui être remboursé. S'agissant des dépens, il conclut à ce qu'ils soient établis à 22'448 fr. 80, dont 5'612 fr. 20 à sa charge et 16'836 fr. 80 à la charge de Mme B.X._, de sorte que cette dernière soit condamnée à lui verser un montant de 11'224 fr. 60. A l'appui de ses conclusions, le recourant se plaint de la violation des art. 91 et 95 CPC et de la violation de son droit d'être entendu (art. 29 al. 2 Cst.). Invitées à se déterminer, la cour cantonale a persisté dans les considérants de son arrêt et l'intimée a conclu, principalement, à ce que le recours soit déclaré irrecevable et, subsidiairement, à ce qu'il soit rejeté.