Faits :
A.
X._, ressortissant suisse né en 1960, a épousé une compatriote, née en 1953, le 25 mars 1983. Quatre enfants sont issus de cette union (1999, 2001, 2002 et 2004). Le 30 novembre 2004, les époux X._ ont annoncé leur départ et celui de leurs enfants de Genève à destination de l'Etat d'Hawaï aux Etats-Unis. Le 25 septembre 2006, ils ont annoncé leur arrivée ainsi que celle de leurs enfants à Genève. Le 5 novembre 2009, leur divorce a été prononcé par la Cour de justice de la République et canton de Genève. Le 26 juillet 2012, X._ a contracté un nouveau mariage à Genève. Le 1 er juillet 2013, il a annoncé son départ pour Monte-Carlo à Monaco. Le même jour, il s'est vu remettre une attestation indiquant qu'il avait résidé sur le territoire genevois entre le 25 septembre 2006 et le 1 er juillet 2013.
Le 15 janvier 2015, X._ s'est rendu auprès de l'Office cantonal de la population et des migrations de la République et canton de Genève (ci-après: l'Office cantonal) pour déclarer qu'il avait en réalité quitté la Suisse en 2006 et n'y était revenu qu'en 2013, pour deux mois. A cette occasion, il a transmis deux courriers manuscrits, l'un rédigé le 26 octobre 2006, mentionnant qu'il quittait la Suisse pour Honolulu, et l'autre le 9 avril 2013, indiquant que sa résidence était à Genève pour quelques mois. Il a affirmé les avoir envoyés à l'Office cantonal qui a répondu ne jamais les avoir reçus.
Le 23 avril 2015, l'Office cantonal a écrit à l'intéressé pour lui dire que s'il désirait faire modifier des données dans le registre des habitants, il devait lui fournir une attestation récente des autorités du pays concerné précisant sa résidence principale du 25 septembre 2006 au 1er juillet 2013, ainsi qu'une attestation fiscale des autorités du pays concerné précisant son assujettissement de 2006 à 2013. Par réponse du 5 juin 2015, X._ a notamment maintenu que l'Office cantonal avait égaré ses courriers et sollicité une modification du registre des habitants, afin qu'il ne figure plus sur celui-ci qu'il avait été domicilié à Genève du 25 septembre 2006 au 1er juillet 2013.
B.
Par décision du 25 juin 2015, l'Office cantonal a refusé de modifier les données du registre des habitants concernant le domicile de X._ pour la période du 25 septembre 2006 au 1er juillet 2013, celui-ci n'ayant pas remis les pièces demandées, les documents déposés à la place ne revêtant pas une force probante suffisante. L'intéressé a contesté ce prononcé devant la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice) le 27 août 2015.
Par arrêt du 1er mars 2016, la Cour de justice a rejeté le recours de X._. Après avoir exclu un cas de violation du droit d'être entendu (motivation de la décision, consultation du dossier) et avoir procédé à une appréciation des moyens de preuve à sa disposition, elle a jugé en bref que l'intéressé n'avait pas apporté la preuve de l'absence de domicile effectif à Genève pour la période du 26 octobre 2006 au 1er juillet 2013. Elle a en conséquence confirmé le refus de modifier l'inscription au registre des habitants.
C.
Agissant par la voie du recours en matière de droit public, X._ demande en substance au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 1er mars 2016 de la Cour de justice et d'ordonner la modification du registre des habitants, afin qu'il en ressorte qu'il n'a pas été domicilié à Genève entre le 26 octobre 2006 et le 9 avril 2013. Il se plaint de violation du droit fédéral et en particulier de violation de son droit d'être entendu.
La Cour de justice persiste dans les considérants et le dispositif de son arrêt. L'Office cantonal n'a pas formulé d'observations et le Département fédéral de justice et police ne s'est pas déterminé. Dans des observations finales, X._ a confirmé ses conclusions.

Considérant en droit :
1.
Le présent litige concerne une modification d'inscription relative au domicile du recourant dans le registre des habitants du canton de Genève pour la période allant du 26 octobre 2006 au 9 avril 2013 (le recourant ayant limité ses conclusions par rapport à l'arrêt entrepris qui étendait la période jusqu'au 1er juillet 2013). La cause relève donc du droit public au sens de l'<ref-law>. La voie du recours en matière de droit public est ouverte, dès lors que la cause ne tombe pas sous le coup de l'une des exceptions prévues à l'<ref-law> et que le registre des habitants ne fait pas partie de la liste exhaustive prévue par l'art. 72 al. 2 let. b ch. 2 LTF qui soumet le recours à la voie du recours en matière civile (cf. CORBOZ, Commentaire de la LTF, Corboz et al. [éd.], 2e éd. 2014, n° 38 ad <ref-law>). Au surplus, le recours, déposé en temps utile (art. 46 al. 1 let. a et 100 al. 1 LTF) et dans les formes requises (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir (<ref-law>), est dirigé contre une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Il est par conséquent recevable.
2.
Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF), alors qu'il n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant, conformément au principe d'allégation (<ref-law>). Dans ce cas, l'acte de recours doit, sous peine d'irrecevabilité, contenir un exposé succinct des droits et principes constitutionnels violés et préciser en quoi consiste la violation (<ref-ruling> consid. 2.5 p. 314; <ref-ruling> consid. 2 p. 248). Par ailleurs, le Tribunal fédéral conduit son raisonnement en se fondant sur les faits constatés par l'autorité précédente (cf. <ref-law>), sous réserve des cas prévus à l'<ref-law>. Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire (<ref-ruling> consid. 2.4 p. 313 s.), et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 4.2 p. 233 s.). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 5.1 p. 356). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal de céans (<ref-law>).
3.
Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant, citant l'art. 29 al. 2 Cst., se plaint de la violation de son droit d'être entendu. Il invoque plus particulièrement une motivation insuffisante de la décision de l'Office cantonal et son droit à consulter le dossier.
3.1. Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, d'avoir accès au dossier, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 4.1.1 p. 52 ss; <ref-ruling> consid. 6.3.1 p. 298 s. et les arrêts cités). L'autorité peut cependant renoncer à procéder à des mesures d'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient l'amener à modifier son opinion (ATF <ref-ruling> consid. 6.3.1 p. 298 s. et les arrêts cités).
Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. implique également pour l'autorité l'obligation de motiver sa décision. Selon la jurisprudence, il suffit que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause. L'autorité n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige. Dès lors que l'on peut discerner les motifs qui ont guidé la décision de l'autorité, le droit à une décision motivée est respecté même si la motivation présentée est erronée. La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (<ref-ruling> consid. 3.2.1 p. 564 s. et les arrêts cités).
Le Tribunal fédéral admet à certaines conditions la possibilité de réparer après coup une violation du droit d'être entendu, en particulier lorsque la décision entachée est couverte par une nouvelle décision qu'une autorité supérieure - jouissant d'un pouvoir d'examen au moins aussi étendu - a prononcée après avoir donné à la partie lésée la possibilité d'exercer effectivement son droit d'être entendu (<ref-ruling> consid. 2.6.1 p. 285; <ref-ruling> consid. 2.2 p. 204 s.).
3.2. En tant que le recourant dirige son grief de violation du droit d'être entendu directement contre la décision de l'Office cantonal, celui-ci doit d'emblée être écarté. Il ne saurait en effet se plaindre d'une telle violation dans le présent recours dirigé contre l'arrêt ultérieur de la Cour de justice, la saisine de cette dernière ayant un effet dévolutif entraînant le dessaisissement de l'instance précédente (cf. arrêt 2C_312/2011 du 26 juillet 2011 consid. 4).
3.3. Le recourant estime encore que la Cour de justice n'a pas examiné le "rapport de renseignement de la police genevoise" qu'il a produit comme pièce et que cette autorité a de ce fait violé son obligation de motiver. Par ce grief, le recourant se plaint bien plus d'une appréciation arbitraire des faits par l'autorité précédente. Toutefois, sa motivation à ce propos, selon laquelle "la Cour de justice aurait dû constater la violation de l'obligation de motiver et d'examiner les griefs par l'Office et renvoyer le dossier à l'Office pour une nouvelle décision", pour autant qu'on la comprenne, ne remplit pas les conditions de motivation posées par l'<ref-law> (cf. consid. 2 ci-dessus). Il convient dès lors d'écarter ce grief sans autre examen.
3.4. Le recourant se plaint finalement de ce que la Cour de justice a confirmé la décision de l'Office cantonal quant au fait qu'il n'aurait pas pu consulter le dossier. Or, il ressort des faits retenus par l'autorité précédente et qui lient le Tribunal fédéral (cf. <ref-law>) que le recourant n'a jamais sollicité la consultation du dossier auprès de l'Office cantonal. Son mandataire a certes proposé d'envoyer un membre de son étude pour procéder à la recherche de ses courriers; il n'a cependant jamais été question de demande formelle d'accès au dossier. Les faits présentés de manière appellatoire à ce propos par le recourant ne sauraient être retenus par le Tribunal fédéral (cf. consid. 2 ci-dessus). Il est dès lors exclu d'admettre une violation du droit d'être entendu dans ces conditions. On relèvera en outre que la Cour de justice a mis à disposition du recourant le dossier de la cause auprès de son greffe. Par conséquent, même s'il fallait reconnaître une violation du droit d'être entendu, celle-ci devrait de toute façon être considérée comme étant réparée.
3.5. Sur le vu de ce qui précède, le grief de violation du droit d'être entendu, tant en ce qu'il concerne la motivation de la décision initiale, respectivement de l'arrêt contesté que la consultation du dossier de la cause, doit être écarté.
4.
Le recourant se plaint finalement de violation du droit fédéral et plus particulièrement de la violation des art. 5 et 11 de la loi du 23 juin 2006 sur l'harmonisation des registres des habitants et d'autres registres officiels de personnes (LHR; RS 431.02), ainsi que de l'<ref-law>.
4.1. Depuis l'entrée en vigueur de la LHR et de l'ordonnance fédérale du 21 novembre 2007 sur l'harmonisation de registres (OHR; RS 431.021), les registres communaux des habitants ne sont plus seulement régis par le droit cantonal et communal (cf. arrêt 2C_173/2012 du 23 août 2012 consid. 3.1). L'art. 11 LHR prévoit dorénavant que les cantons édictent les dispositions nécessaires, afin que toute personne physique qui déménage s'annonce au service du contrôle des habitants dans les quatorze jours qui suivent l'événement (let. a); toute personne tenue de s'annoncer communique, de façon conforme à la vérité, les données énumérées à l'art. 6 LHR ainsi que, le cas échéant, les documents nécessaires (let. b). Les registres doivent contenir des données actuelles, exactes et complètes par rapport à l'ensemble des personnes visées (art. 5 LHR).
Dans le canton de Genève, l'ancienne loi genevoise du 16 juillet 1881 concernant le contrôle de la population a ainsi été abrogée par l'entrée en vigueur, le 3 novembre 2009, de la loi genevoise du 3 avril 2009 d'application de la loi fédérale sur l'harmonisation des registres des habitants et d'autres registres officiels de personnes (LaLHR/GE; RSGE F 2 25; cf. art. 13 LaLHR/GE).
4.2. La LHR définit à présent la commune d'établissement comme celle dans laquelle une personne réside, de façon reconnaissable pour des tiers, avec l'intention d'y vivre durablement et d'y avoir le centre de ses intérêts personnels. Une personne est réputée établie dans la commune où elle a déposé le document requis. Elle ne peut avoir qu'une commune d'établissement (art. 3 let. b phr. 1 LHR). La commune de séjour est celle dans laquelle une personne réside dans un but particulier sans intention d'y vivre durablement, mais pour une durée d'au moins trois mois consécutifs ou répartis sur une même année; il s'agit notamment de la commune dans laquelle une personne séjourne pour y fréquenter les écoles ou se trouve placée dans un établissement d'éducation, un hospice, un hôpital ou une maison de détention (art. 3 let. c LHR).
Selon la jurisprudence, l'établissement et le séjour, le domicile civil et les domiciles spéciaux sont déterminés par des autorités différentes dans des procédures distinctes (cf. arrêts 2C_791/2011 du 4 avril 2012 consid. 1.3; 2C_478/2008 du 23 septembre 2008 consid. 3.5). La plupart du temps, c'est le domicile civil qui sert de point de référence aux autres domaines du droit. Le message du Conseil fédéral du 23 novembre 2005 concernant l'harmonisation de registres officiels de personnes précise ainsi expressément que l'art. 3 let. b LHR donne de l'établissement une définition qui s'appuie notamment sur la définition du Code civil suisse (cf. FF 2006 439 p. 469).
En droit civil, selon l'<ref-law>, le domicile de toute personne est au lieu où elle réside avec l'intention de s'y établir. Lorsque la détermination du domicile d'une personne soulève des difficultés, tant le critère de l'intention de s'établir que la notion de centre de vie commandent de recenser tous les facteurs qui pourraient s'avérer importants. Chacun de ces facteurs, pris en lui-même, ne constitue donc rien de plus qu'un indice. Ainsi, le dépôt des papiers au contrôle de l'habitant, l'établissement du permis de séjour, l'exercice des droits politiques, le paiement des impôts ne sont jamais déterminants en eux-mêmes pour fonder le domicile civil volontaire. Les constatations relatives à ces circonstances relèvent du fait, mais la conclusion que le juge en tire quant à l'intention de s'établir est une question de droit (cf. <ref-ruling> consid. 4.3 p. 409 s. et les références citées).
Il découle de la jurisprudence précitée que c'est régulièrement le domicile civil et les domiciles spéciaux qui permettent d'établir si une personne est établie dans une commune donnée au sens de l'art. 3 let. b LHR, et non l'inverse (arrêt 2C_791/2011 du 4 avril 2012 consid. 1.3). Il ne faut cependant pas perdre de vue que le Code civil et la loi sur l'harmonisation des registres poursuivent des buts différents (arrêt 2C_919/2011 du 9 février 2012 consid. 3.2).
4.3. En l'espèce, le recourant estime que la Cour de justice a procédé à une mauvaise application de la législation en matière d'annonce de départ et d'arrivée des citoyens. Il est d'avis qu'elle a apprécié faussement les éléments de preuve fournis pour en déduire qu'il n'avait pas valablement annoncé son départ en 2006. Selon le recourant, il bénéficie du droit de faire rectifier un registre erroné pour qu'il corresponde à la réalité, conformément à l'art. 5 LHR.
Pour sa part, la Cour de justice a considéré que les pièces produites permettent certes de constater que le recourant a été amené à voyager et à résider dans différents lieux pour des raisons professionnelles ou personnelles, mais que ces pièces ne permettent pas d'établir à suffisance que le recourant aurait déplacé sa résidence effective hors du canton de Genève durant la période litigieuse. L'autorité précédente a retenu que, malgré les nombreuses demandes effectuées par l'Office cantonal, le recourant n'a pas produit d'attestation des autorités du pays concerné précisant le lieu de sa résidence principale ainsi qu'une attestation fiscale des autorités compétentes précisant son assujettissement pour la période en cause. Le recourant a certes déposé diverses pièces, mais celles-ci, selon l'appréciation de la Cour de justice, ne sont pas pertinentes. De plus, les juges cantonaux ont encore mentionné que les nombreuses pièces figurant déjà au dossier, par exemple un jugement de divorce du 5 novembre 2009 et un extrait de l'état civil du 26 juillet 2012 faisant tous deux état d'un domicile du recourant à Genève, une décision relative à des allocations familiales perçues pour l'année 2009 que le recourant ne conteste pas avoir reçue à son domicile genevois ou un courrier du 15 juillet 2011 rédigé par le mandataire du recourant et indiquant que celui-ci vivait à son adresse genevoise, permettent de conclure que le recourant était effectivement domicilié dans le canton de Genève durant la période litigieuse. Rien ne fait état d'une contestation de cette domiciliation dans ces documents. La Cour de justice a surtout mentionné que le recourant a sollicité à plusieurs reprises durant les années litigieuses des attestations auprès de l'Office cantonal, lesquelles indiquent toutes qu'il résidait à Genève depuis le 26 octobre 2006. Or, celui-ci n'a pas entamé de démarches pour faire modifier cette inscription avant le mois de janvier 2015.
4.4. Sous couvert de violation des art. 5 et 11 LHR, respectivement 23 CC, le recourant conteste en réalité l'appréciation des moyens de preuve effectuée par l'autorité précédente. Il méconnaît toutefois que le Tribunal ne revoit l'établissement des faits et l'appréciation des preuves que sous l'angle restreint de l'arbitraire (cf. consid. 2 ci-dessus). Or, le recourant ne fait à aucun moment valoir une appréciation arbitraire des preuves par la Cour de justice. Il substitue bien plus, de manière purement appellatoire, ses vision et appréciation des faits à celles de l'autorité précédente. Au demeurant, quand bien même il aurait invoqué l'arbitraire et motivé son recours conformément au principe de l'invocation de l'<ref-law>, force serait malgré tout de constater que l'appréciation effectuée par la Cour de justice, dont les éléments principaux ont été repris ci-dessus (consid. 4.3), est pleinement soutenable et ne saurait être considérée comme arbitraire.
En conséquence, il faut admettre que le recourant n'a pas fourni des indices suffisants pour démontrer que son domicile ne se trouvait pas dans le canton de Genève entre le 26 octobre 2006 et le 9 avril 2013. C'est donc sans violer la LHR, et en particulier l'art. 3 let. b LHR, que l'autorité précédente a confirmé le refus de modifier le registre des habitants dans le sens voulu par le recourant. Pour le surplus, dans la mesure où le recourant désirait invoquer la violation de dispositions de droit cantonal (que ce soit la LaLHR/GE, l'ancienne loi genevoise du 16 juillet 1881 concernant le contrôle de la population ou toute autre loi cantonale), force est de constater que sa motivation ne remplit pas les conditions posées par l'<ref-law> (cf. <ref-ruling> consid. 1.2 p. 382 s.).
5.
Sur le vu de ce qui précède, le recours doit être rejeté. Succombant, le recourant doit supporter les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, à l'Office cantonal de la population et des migrations et à la Cour de justice de la République et canton de Genève, Chambre administrative, 2 ème section, ainsi qu'au Département fédéral de justice et police.
Lausanne, le 3 octobre 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette